Backtracking is recursive search through a tree of partial solutions. At each step, extend the current partial solution by one choice; if the choice leads to a dead end, undo it and try a different one. The "backtrack" is the undo.
The template
``` function backtrack(state, choices): if state is a complete solution: record(state) return for choice in valid_choices(state): apply choice to state backtrack(state, choices) undo choice on state # the backtrack step ```
Pruning
Without pruning, backtracking is just exhaustive enumeration — or worse. With smart pruning ("this branch can't possibly reach a valid solution"), the effective search space shrinks dramatically. Pruning early matters more than micro-optimizing the inner loop.
Classic problems
- Subsets: at each index, include or exclude. leaves in the tree.
- Permutations: at each step, pick any remaining element. leaves.
- N-Queens: place a queen in each row; prune rows where the queen attacks an existing one. Without pruning, states; with pruning, far less.
- Sudoku: at each empty cell, try 1-9; prune values that conflict with the row/column/box.
- Word search in a grid: DFS from each cell; prune when the next character doesn't match.
In-place state management
Mutating shared state and undoing it on return is more memory-efficient than passing a fresh copy each call. Be disciplined: every mutation in the recursive case needs a matching undo after the recursive call.
Backtracking vs DFS
Backtracking is DFS through a search space where nodes are partial solutions and edges are extensions. The "visited" check is often implicit (we're exploring a tree, not a graph). The key difference from generic DFS: backtracking explicitly undoes choices, enabling efficient exploration without copying state.