Backtracking is the polite brute force: make a choice, explore it to the end, then undo it as if you were never there. The recursion tree visits every candidate — and pruning teaches it to slam the door on doomed ones early.
Every pattern so far exploited some structure — sortedness, monotonicity, a hierarchy, a frontier. This chapter is for when there is none: the problem says all of them, and the only honest move is to try everything. Backtracking is how you try everything without drowning — one shared, mutable partial answer, extended and retracted, walking an exponential tree in linear memory.
It's the last stop in Part IV for a reason: backtracking is just Chapter 11's DFS pointed at an imaginary tree — the tree of choices instead of a tree of nodes. Learn one skeleton here and you've solved Subsets, Permutations, Combination Sum, Word Search, Palindrome Partitioning, and N-Queens. They differ in exactly two lines: what counts as a choice, and what you refuse to try.
Suppose the problem asks for all subsets, all permutations, every valid arrangement. There's no shortcut hiding in the statement — the answer itself is exponentially large, so any algorithm must at least touch every answer. The naive way to do that is to materialize candidates: build every string of n choices, then filter the legal ones. That drowns fast, because most of those candidates were doomed at choice two.
Backtracking builds candidates incrementally instead. Keep one partial answer — a growing path. At each step, enumerate the choices legal right now, apply one, recurse, and then — the signature move — undo it and try the next. The undo is what makes it brute force with manners: every branch inherits a clean state, and the whole exponential search runs in O(depth) extra memory — one path, reused a billion times.
And because a doomed partial answer is detected at depth two instead of depth twenty, whole subtrees vanish before they're born. That's pruning, and it's Section 5's whole job.
Picture every partial answer as a node: the root is the empty path, each edge is one choice, each leaf is a complete candidate. For Subsets Medium on [1,2,3], every element gets a binary verdict — in or out — so the tree is a full binary tree of depth 3 with 2³ = 8 leaves, one per subset.
Here's the part that makes backtracking cheap to write: you never build this tree. It exists only as the trace of your recursion. The call stack holds exactly one root-to-current-node path at any moment; "choose" walks down an edge, "un-choose" walks back up. Chapter 11 said pre-order and post-order are about when you look at a node — choose is your pre-order moment, un-choose is your post-order moment. Same DFS, imaginary tree.
Walk it live. Solid green edges take an element, dashed grey edges skip it; watch the ochre path snake down, retreat, and snake down again — and watch the eight subsets drop out of the leaves in DFS order.
Strip every backtracking solution to its spine and you find the same three lines inside a loop over choices:
Why mutate-and-undo instead of passing fresh copies down? Copies are correct — and in a pinch they're a fine way to get unstuck — but copying an O(n) path at every one of 2ⁿ nodes buys you an extra factor of n and a garbage-collector workout. The undo version pays O(1) per edge. More importantly, the undo is the backtrack: returning from the recursion physically re-enters the parent's world. When people say "then we backtrack", this pair of lines is the thing they're saying.
The three "generate all…" staples are the same skeleton wearing different choice lists:
The start index versus the used array is the entire difference between "order doesn't matter" and "order matters" — one integer versus one boolean array. Generate Parentheses Medium is the same skeleton again with exactly two choices per node: add ( if any remain, add ) if it wouldn't overrun.
Duplicate inputs get one extra move: sort first, then skip equal neighbors at the same depth — if i > start and nums[i] == nums[i-1]: continue. That single line deduplicates Subsets II and Combination Sum II without a set of seen-answers in sight. (Chapter 5 played the same skip-duplicates card in 3Sum — sorted input keeps paying rent.)
Backtracking's superpower isn't visiting the tree — it's refusing most of it. A prune is a test you run before recursing: if this choice provably cannot lead to any answer, don't take the edge at all. The whole subtree below it — possibly thousands of nodes — evaporates for the cost of one comparison.
Combination Sum Medium makes the arithmetic visible. Target 8 from candidates [2,3,5], reuse allowed. Carry remaining down the tree. Without pruning, you descend into hopeless branches and discover the overshoot after arriving (remaining goes negative — a dead end you paid full price to visit). With pruning, one glance — candidate > remaining — refuses the branch at the door. And because the candidates are sorted, that's a break, not a continue: if 3 is too big, 5 certainly is.
Run it both ways and read the node counters. Same answers, same skeleton — different bill.
Once you see "choices at a node", backtracking escapes the arrays-of-numbers ghetto:
N-Queens Hard is the pattern's graduation exam: place n queens on an n×n board so none attack. The framing that makes it easy is choosing the tree shape well — one queen per row, rows top to bottom. Then a node at depth r means "rows 0..r−1 are safely placed", the choice list is "columns in row r", and the prune is constraint checking: a column, a ↘ diagonal (r − c constant), or a ↗ diagonal (r + c constant) already claimed → refuse. Three hash sets, O(1) per test.
The drama is the retreat: sometimes every column in row r is attacked. That's not failure, that's information — the recursion returns, the parent un-chooses its queen and tries her one column to the right. Watch the auto-solver below do exactly this; the backtrack counter is the number of times a placed queen had to be taken back. Sudoku Solver Hard is the same machine with 9 choices per empty cell and row/column/box sets as the prune — bigger board, identical liturgy.
You can also play interviewer: click squares to place queens by hand and watch the attack rays find your conflicts.
Backtracking's honest price list: O(n · 2ⁿ) for subset-shaped trees, O(n · n!) for permutation-shaped ones — "every candidate, copied once". Chapter 3's constraint sniffing turns that into a go/no-go call in seconds: 2ⁿ is fine to about n = 20; n! dies around n = 10. If the constraints say n ≤ 15, the interviewer has pre-approved your exponential — say so, out loud, and it counts as analysis.
The boundary to respect is with Chapter 20. If the problem wants the objects themselves — the actual subsets, the actual boards — the output is exponential and backtracking is the only game. But if it wants only a count or a best value ("how many ways", "minimum cost"), and the subproblems repeat, then enumerating every way is a war crime against the CPU: DP computes the count without touching the ways. Backtracking + caching on repeated states is memoization — which is to say, Chapter 20 is what happens when this chapter's tree starts rhyming with itself.
The pattern, as a whiteboard skeleton:
Subsets Medium is the flagship because it's the skeleton with nothing else attached — no size check, no dedup, no prune. Read the three commented lines in the loop; they are the entire pattern. Then read the permutations function directly below it and notice what changed: the choice list (start index became a used array) and the collect condition. Nothing else. That delta is the whole of Section 4, executable.
The Scala pane adds a treat: the pure-FP fold that builds all subsets in three lines. Admire it, then put it away — the interview wants the skeleton, because the skeleton is the one that generalizes to Combination Sum, Word Search, and N-Queens by swapping two lines.