Loading...
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.
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:
Click any topic to jump in
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.
The two canonical shapes: choose $k$ from $n$ (order-free) and order $n$ items (order matters).
Cut branches that cannot satisfy constraints — turns exponential search spaces into tractable ones.
Generate the Cartesian product of digit-to-letter sets — a clean application of the combinatorial template.
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.
Two equivalent approaches — visited-array tracking versus in-place swap — with the same $\Theta(n \cdot n!)$ cost.
When the backtrack tree has overlapping subproblems, caching collapses exponential work to polynomial.
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.
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].
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.