Backtracking
Backtracking systematically explores all candidate solutions by building them one choice at a time and abandoning a partial candidate the moment it cannot possibly succeed. It is a refined brute force that skips huge portions of the search space.
The pattern
At each step you choose an option, explore the consequences by recursing deeper, then undo the choice before trying the next one. This choose, explore, unchoose rhythm is the signature of backtracking. The undo restores state so siblings start from a clean slate.
The key efficiency comes from pruning: if a partial solution already violates a constraint, you stop and back up immediately rather than completing a doomed candidate. Solving the N queens puzzle and Sudoku both rely on this.
When to use it
Reach for backtracking on constraint satisfaction and combinatorial problems like permutations, subsets, and path finding in a maze. The worst case can still be exponential, but good pruning often makes real inputs tractable.
Key idea
Backtracking grows candidates step by step and prunes dead ends early, exploring far fewer possibilities than blind brute force.