Chapter 5: Backtracking
Explore systematic search through decision spaces using backtracking. Learn how to enumerate subsets, combinations, and permutations by building partial solutions incrementally, pruning invalid branches early, and applying memoization when subproblems overlap.
Chapter Overview
Backtracking is a refined form of brute-force search. Instead of generating every possible solution and then checking validity, backtracking builds solutions incrementally---placing one element at a time---and abandons a partial solution as soon as it determines that it cannot possibly lead to a valid answer.
The key idea is a state-space tree: each node represents a partial solution, each edge represents a decision (include an element, pick a digit, place a queen), and each leaf is a complete candidate. DFS traverses this tree, and pruning cuts off entire subtrees when constraints are violated, dramatically reducing the search space.
Backtracking problems share a common template: choose a candidate, recurse with the updated state, then undo the choice (backtrack) before trying the next candidate. Mastering this template unlocks an entire class of interview problems---from generating subsets and permutations to solving constraint-satisfaction puzzles like N-queens and Sudoku.
This chapter covers:
- State-space trees: Visualizing the decision tree and understanding how DFS explores it
- Combinatorial generation: Subsets, combinations, and permutations using systematic enumeration
- Pruning strategies: Cutting invalid branches early to avoid unnecessary work
- Classic backtracking problems: Phone letter combinations, valid parentheses, and word break
- Deduplication: Handling duplicate elements without producing duplicate results
Chapter Roadmap
Click any topic to jump in
DFS with States
Every backtracking algorithm is a DFS over a state-space tree — nodes are partial solutions, edges are choices.
Combinations and permutations are the two fundamental shapes that map to the DFS template.
Combinations & Permutations
The two canonical shapes: choose $k$ from $n$ (order-free) and order $n$ items (order matters).
Pruning
Cut branches that cannot satisfy constraints — turns exponential search spaces into tractable ones.
Letter Combinations
Generate the Cartesian product of digit-to-letter sets — a clean application of the combinatorial template.
Generate Parentheses
Count of valid strings is the $n$-th Catalan number; the backtrack tree grows with constraint-guided pruning.
Each classic problem picks a different strategy — unrestricted product, constraint-driven, or choice-tracking.
Permutation Strategies
Two equivalent approaches — visited-array tracking versus in-place swap — with the same $\Theta(n \cdot n!)$ cost.
Memoization
When the backtrack tree has overlapping subproblems, caching collapses exponential work to polynomial.
Deduplication
Sort and skip — the standard way to avoid generating the same subset or permutation twice.
Backtracking is DFS on a state-space tree, where each node represents a partial solution and each edge represents a decision. At every node you decide whether to include or exclude an element, then recurse deeper. When you reach a leaf (a complete decision for every element), you record the result and backtrack by undoing your last choice.
The classic example is generating all subsets of a set. For n elements there are 2^n subsets, because each element is either included or excluded. The state-space tree has depth n and each node branches into two children---one where the element is included and one where it is not.
In this topic
State-Space Tree
A state-space tree is an abstract tree where each path from root to leaf represents a sequence of decisions that builds one complete candidate solution. The root is the empty state (no decisions made). At each level, you decide what to do with the next element---include it, exclude it, or choose from a set of options. DFS explores this tree, visiting every path. The total number of leaves equals the total number of candidate solutions.
A backtracking algorithm is a DFS over a state-space tree whose nodes are partial solutions and whose edges represent extending a partial solution by one choice. If each node has at most children (branching factor) and depth is at most , the tree has at most leaves and nodes. Work per node is at least to copy the state, so total time is — inherently exponential without pruning.
Visualize the state-space tree for generating all subsets of [1, 2, 3].
Backtracking Template
The backtracking template has three core steps repeated at each node: (1) Choose --- add a candidate to the current partial solution. (2) Explore --- recurse to the next decision level. (3) Unchoose --- remove the candidate (backtrack) before trying the next option. This choose-explore-unchoose cycle ensures every branch of the state-space tree is visited while keeping the shared state clean between branches.
The template is: if state is a solution, record it and return; for each choice, apply it (mutate state), recurse, undo it (restore state). Undoing is what makes 'backtracking' — it reuses one mutable buffer across the entire traversal for extra memory. The total time remains but the constants are smaller than building new states.
Generate all subsets of a list using the backtracking template.