Backtracking

Backtracking walks a decision tree that never exists in memory. Each call makes one choice, recurses, then undoes it, so the search only ever holds a single path and reuses the same small state for every branch.

Variant	Shape of the tree	Typical use
Take or leave	Two branches per element	Subsets, XOR over subsets
Pick the next	One branch per unused element	Permutations, orderings
Cut and continue	One branch per legal next piece	Target sums, word splits, queens

The whole game is pruning. Sorting the input lets you stop a loop early as soon as the running sum passes the target. Passing a start index avoids revisiting earlier positions, while a used-elements array and skipping equal adjacent values prevent duplicate branches. When different branches repeatedly land on the same state, caching the result by state turns the search into dynamic programming.

Approach	Time	Extra space
Generate everything, then filter	$O(2^n)$ or $O(n!)$	$O(\text{output})$
Backtrack with pruning	Size of the surviving tree	$O(n)$ for the path
Backtrack with memo	$O(\text{states} \cdot \text{choices})$	$O(\text{states})$

Reach for it when a problem wants every subset, arrangement, or placement that satisfies a rule (or the count of them), and $n$ is small enough that the pruned tree fits in the time limit.

The problems below start with subsets and permutations, move through duplicate skipping, target sums with sorted pruning, and memoized word splitting, and end with counting non-attacking queen placements.