Backtracking
01 / The one-sentence essence
Explore a decision tree depth-first, undo each choice on the way back up — so the same array, the same recursion frame, and the same path build every candidate in turn.
Problemenumerate all subsets of a setInput[1, 2, 3]2ⁿ8
emitted— nothing yet —
Start at the root with subset [ ]. Decide each element: include or exclude.
step
0 / 15
depth
0
current subset
[ ]
emitted
0
0 / 15
02 / The pattern signature
# DFS over a tree of decisionsbacktrack(state, depth):if at a leaf or pruned: record / discard; returnfor each choice at this depth:// 1. extend the stateapply choice to statebacktrack(state, depth + 1)// 2. undo before trying the next siblingrevert choice from state
03 / When to recognize this pattern
"all / every"
You need to enumerate every valid configuration, not find one optimal answer. The problem cares about completeness.
"build a sequence"
The answer is a sequence of decisions — pick element, pick row, pick character — and the decisions interact.
"satisfies a constraint"
Each partial state can be validated incrementally — you can prune whole subtrees early when the constraint already fails.
"factorial / exponential"
The problem statement says the search space is huge but the constraints make most of it unreachable — pruning is what makes it tractable in practice.
04 / Common pitfalls
i.
Forgetting to undo the choice before trying the next sibling.
The "back" in backtracking is the part everyone forgets. If
state isn't restored after a recursive call returns, you carry stale state into the sibling branch — producing wrong subsets, duplicate solutions, or invalid boards.ii.
Storing references instead of copies at the leaf.
When you record a result, push a
copy of the running state — not a reference to it. The recursion will keep mutating that state, and your collected result will mutate with it.iii.
Missing the early-prune check.
The naive version explores the whole tree — exponential. The fast version checks before descending whether the partial state can still lead to a solution, and skips the subtree if not. For most problems, pruning is the difference between fast and unusable.
05 / Go practice — on LeetCode
Four problems, ordered by branching difficulty. Subsets is the binary tree above; the rest have wider branching and rely on pruning to stay fast.