Module 13
Backtracking
Build answers one choice at a time, undo the last choice, and try the next: subsets, permutations, combinations, puzzles and grid searches.
Backtracking explores a tree of decisions. At each step you choose an option, explore everything that follows from it, then undo the choice so the next option starts from a clean state. It's recursion plus one discipline: always clean up after yourself.
The module gives you three templates (subsets, permutations, combinations) that cover most interview problems, then shows how to prune branches early and how to avoid duplicate answers. Expect exponential time: these problems have small inputs because the answers themselves are exponential.
Best after: Recursion
Part 1
Learn the ideas
- 13.1Choose, Explore, UnchooseEvery backtracking function adds a choice to the current path, recurses, then removes it. Draw the decision tree first.15 min
- 13.2Subsets, Permutations and CombinationsA `start` index gives subsets and combinations (order doesn't matter); a `used[]` array gives permutations (order matters).14 min
- 13.3Pruning and Avoiding DuplicatesStop branches that can't succeed, and when the input has duplicates, sort it and skip equal values at the same depth.14 min
- 13.4Backtracking on GridsMark a cell as used before exploring its neighbours and restore it afterwards, so other paths can use it.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The base template: record every path, extend only with later elements.
Duplicates in the input: sort, then skip equal values at the same depth.
When order matters, any unused element can go next: track usage with a boolean array.
Reusable elements (recurse with i, not i + 1) and pruning with a sorted array.
One decision per position, with the options given by a lookup table: a product of choices.
Prune with counts: add '(' while some remain, add ')' only when it would still be balanced.
Grid backtracking: mark the cell, explore four neighbours, restore the cell.
Backtracking over cut positions, choosing only cuts that leave a palindrome piece.
Place one queen per row and prune with sets of used columns and diagonals for O(1) attack checks.
Fill empty cells one at a time, check row/column/box constraints in O(1), and backtrack on contradictions.