Recursion and Backtracking
Not started yet — 14 problems queued; the direct prerequisite for tree recursion in Trees.
Explore all candidates by making a choice, recursing, then undoing the choice (backtrack) — building a decision tree, and pruning branches early once constraints are violated to avoid wasted exploration. The key distinction: subsets include/exclude each element, permutations track what's used since order matters, combinations choose k without revisiting earlier indices.
Sub-patterns
- A — Subsets. Include/exclude each element.
- B — Permutations. Order matters — track what's already used.
- C — Combinations. Choose k, never revisit earlier indices.
- D — Constraint Satisfaction. Board-placement problems like N-Queens and Sudoku.
- E — Partitioning. Split a sequence into valid pieces.
- F — String Backtracking. Build strings choice-by-choice, e.g. parentheses or phone-letter combinations.
Practice set (14)
- Medium — Subsets, Subsets II, Permutations, Combinations, Combination Sum, Combination Sum II, Palindrome Partitioning, Letter Combinations of a Phone Number, Generate Parentheses, Word Search
- Hard — N-Queens, Sudoku Solver, Word Search II, Word Break II
Subsets
Include/exclude each element to build every subset.
Permutations
Order matters here — track what's already used at each step of the recursion.
Combinations
Choose k elements, never revisiting earlier indices.
Constraint Satisfaction
Board-placement problems like N-Queens and Sudoku — prune as soon as a constraint is violated.
Partitioning
Split a sequence into valid pieces, backtracking over where each split lands.
String Backtracking
Build strings choice-by-choice — parentheses generation, phone-letter combinations.
Notes from readers
Comments — via GitHub