Recursion and Backtracking
Recursion mental model, backtracking templates, divide-and-conquer, permutations, combinations, subset generation. Pre-DP.
- Chapters
- 7
- Hours
- 2
- Difficulty
- Intermediate to Advanced
- 7.0intermediate
Recursion patterns: linear, tree, and divide-and-conquer
Three call-tree shapes — linear, tree, divide-and-conquer — and how to read the shape from the recursive case so you know whether you need memoization, an accumulator, or neither.
- 7.1intermediate
The backtracking template
Choose, recurse, unchoose, with prune-on-partial-information as the move that turns exponential search into something that finishes.
- 7.2intermediate
Subsets, combinations, permutations
One recursion with three knobs (when to snapshot the path, what to skip, when to allow repeats) covers subsets (LC 78), permutations (LC 46), and combination sum (LC 39).
- 7.3advanced
N-Queens: pruning and constraint propagation
Column and diagonal occupancy bitsets give O(1) attack checks. Symmetry pruning and the constraint-propagation idea that generalizes to Sudoku and beyond.
- 7.4advanced
Sudoku solver: constraint propagation and forward checking
Row, column, and box bitmasks combined with MRV cell selection and a forward-checking loop solve a 9x9 in milliseconds, despite 4 × 10^38 candidate fillings.
- 7.5intermediate
Word search and grid backtracking
Grid DFS with mark-and-restore: the in-place visited trick that turns a 2D backtracking problem into one clean recursion.
- 7.6advanced
Randomized algorithms: Fisher-Yates, reservoir sampling, rejection sampling
Three randomized recipes — Fisher-Yates shuffle, reservoir sampling, rejection sampling — whose proofs of uniform correctness are the actual lesson, not the code.