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
Input
1
2
3
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
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.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.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
medium23
01Letter Combinations of a Phone Number— LC 17→02Generate Parentheses— LC 22→03Next Permutation— LC 31→04Valid Sudoku— LC 36→05Combination Sum— LC 39→06Combination Sum II— LC 40→07Permutations— LC 46→08Permutations II— LC 47→09Combinations— LC 77→10Subsets— LC 78→11Word Search— LC 79→12Subsets II— LC 90→13Restore IP Addresses— LC 93→14Palindrome Partitioning— LC 131→15Combination Sum III— LC 216→16Combination Sum IV— LC 377→17Matchsticks to Square— LC 473→18Non-decreasing Subsequences— LC 491→19Beautiful Arrangement— LC 526→20Partition to K Equal Sum Subsets— LC 698→21Brace Expansion— LC 1087→22Path with Maximum Gold— LC 1219→23Maximum Length of a Concatenated String with Unique Characters— LC 1239→
hard12
01Sudoku Solver— LC 37→02N-Queens— LC 51→03N-Queens II— LC 52→04Permutation Sequence— LC 60→05Palindrome Partitioning II— LC 132→06Word Break II— LC 140→07Word Search II— LC 212→08Expression Add Operators— LC 282→09Remove Invalid Parentheses— LC 301→10Robot Room Cleaner— LC 489→11Unique Paths III— LC 980→12Maximum Number of Achievable Transfer Requests— LC 1601→