Backtracking
Systematically explore all possible candidates and abandon ("backtrack") as soon as you determine the current path cannot lead to a valid solution.
Core Concepts
Backtracking is a refined form of brute force — it prunes the search tree by abandoning paths early. Classic problems include:
- Permutations: Generate all orderings of n elements (n! possibilities).
- Combinations: Choose k elements from n without repetition (n choose k).
- Subsets: Generate all 2^n subsets of a set.
- N-Queens: Place n queens on n×n board so none attack each other.
- Sudoku Solver: Fill a 9×9 grid satisfying all constraints.
- Word Search: Find a word in a 2D grid using DFS + backtracking.
Cheatsheet Formulas
- Template:
choose → explore(next) → unchoose— always undo the choice after recursion - Permutations time: O(n!) space: O(n) for call stack
- Combinations time: O(C(n,k) * k) — k for copying each result
- Pruning: Add
if (invalid(state)) return;as early as possible to cut branches - Visited set: Use a boolean array or bit mask to track used elements in O(1)
- Avoid duplicates: Sort first, then skip
if (i > start && nums[i] == nums[i-1]) continue;