Backtracking

Backtracking builds a solution one choice at a time, explores each choice with recursion, and undoes it before trying the next, so it can search every valid answer without storing them all.

To list every subset, decide for each element whether it is in or out; a set of n elements has 2^n subsets, and backtracking generates them in O(n * 2^n).

A permutation is an ordering of all the elements; n distinct elements have n! orderings, and backtracking builds them position by position using a used array.

Combination problems pick unordered groups that meet a rule such as size k or a target sum; the start index prevents reordered duplicates, and a running remainder lets you stop early.

Constraint puzzles fill a board one cell or row at a time, check the rules before each placement using fast lookup sets, and backtrack the moment a rule would be broken.

Pruning cuts off branches of the search tree that cannot lead to a valid or better answer, which is what makes exponential backtracking fast enough in practice.