Lesson 14 of 16 · 12:59
Recursive backtracking
Backtracking searches a decision tree. A node is a partial candidate, an edge is one legal choice, and a leaf may be a completed answer. The algorithm makes a choice, explores everything below it, and undoes the choice so another branch begins from the correct state.
The implementation is usually short, but the reasoning is in the state definition: which choices are available, what makes a candidate complete, what makes a partial candidate impossible, and which mutable data must be restored.
What you should be able to do after this lesson
- Define one recursion level as one decision
- Restore shared state exactly
- Prune only with a proof that no valid descendant remains
The mental model
Every recursive level owns one decision. The path is the exact sequence of choices on the current root-to-node branch—not a global bag of choices.
Recognize it when: Use backtracking when asked to generate or test combinations, permutations, subsets, placements, partitions, or paths under constraints.
The invariant to say aloud: On entry, path contains exactly the decisions made by ancestors; on return, the function restores path and all auxiliary state to that same condition.
Learn the ideas one at a time
Concept 1 of 5
Decision tree
Watch from 0:00 ↗Each edge is a choice and each level is a decision position. Leaves are complete candidates; internal nodes are partial candidates.
Choose a recursion state that uniquely describes the partial solution and remaining decisions. For permutations, a level may choose the next position; for subsets, it may decide whether to include the current item. Different formulations can generate the same answers with very different duplicate behavior.
Walk through an example
For choices A and B, the root path [] branches to [A] and [B]. From [A], only B remains; from [B], only A remains. Leaves [A,B] and [B,A] are complete permutations.
In an interview
Draw two levels before coding. If the edges and completion rule are unclear on paper, the recursive parameters are not ready.
Concept 2 of 5
Choose / explore / undo
Watch from 0:00 ↗Mutate the path, recurse, then reverse the mutation. Undo is what lets one shared path represent many branches safely.
A shared path avoids allocating a new list at every edge, but it creates a restoration obligation. Append a choice, recurse, then pop that exact choice even when the branch yields no answer. Other state such as used flags and counts must be restored symmetrically too.
Walk through an example
Path [A] chooses B and explores [A,B]. On return, pop B so path is [A], then pop A before exploring the root's B branch. Without undo, branches contaminate one another.
In an interview
Pair every mutation with its inverse in adjacent visual structure. This makes restoration auditable.
Concept 3 of 5
Base case and capture
Watch from 0:00 ↗When a candidate is complete, append a copy of the path. Appending the same mutable list reference makes all recorded answers change later.
The base case recognizes a complete candidate and records a snapshot. Because path is mutated later, append a copy such as path.copy(), not the same list object. Decide whether to return immediately or whether a complete candidate may still be extended.
Walk through an example
Appending path twice stores two references to one list; later pops make both recorded answers appear empty. Copying freezes the values at the leaf.
In an interview
State what makes a solution complete and whether the problem wants exact length, any valid prefix, or all extensions.
Concept 4 of 5
Pruning
Watch from 0:00 ↗Reject a branch as soon as a constraint proves no descendant can succeed. Good pruning reduces explored nodes without removing valid answers.
Pruning stops a branch only when a constraint proves that every descendant fails or cannot improve the best answer. Sorting choices may enable stronger pruning, such as breaking once later values can only make a sum larger. Incorrect pruning silently removes valid answers.
Walk through an example
If all remaining numbers are nonnegative and a partial sum already exceeds the target, adding more cannot repair it, so the branch is safely abandoned.
In an interview
Give the implication behind each prune: condition C means no continuation can succeed. Avoid heuristic pruning unless approximation is allowed.
Concept 5 of 5
Complexity
Watch from 0:00 ↗Runtime is proportional to the explored decision tree and often exponential or factorial, plus the cost of copying each output.
Time follows the number of explored decision-tree nodes, not just recursion depth. Subsets produce about 2^n leaves; permutations produce n! leaves. Producing each answer can add O(n) copy cost, and pruning improves observed work without necessarily changing the worst-case class.
Walk through an example
A binary include/exclude decision at each of n positions creates 2^n leaves. Copying an n-item path at many leaves adds output-proportional work that cannot be avoided if all answers must be returned.
In an interview
Express complexity as branching factor^depth when exact counting is hard, then include output construction and O(depth) stack/path space.
Before you call this lesson done
- Define level, choices, and completion
- Pair choose with undo
- Copy mutable answers
- Prove every prune and count output cost
