Backtracking
Explore all candidates by building solutions incrementally and abandoning paths that can't lead to valid answers.
- • Generate all permutations/combinations/subsets
- • Constraint satisfaction (Sudoku, N-Queens)
- • Path finding with constraints
- • Counting problems (use DP)
- • Finding a single optimum (use greedy/DP)
- • Forgetting to undo choices (backtrack)
- • Not pruning early enough
- • Duplicate results from equivalent branches
Key Invariant
Choose → Explore → Unchoose — always undo the last choice before trying the next branch