A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
Backtracking is depth-first search over a tree of decisions that you never build. Each node is a partial answer, each edge is one choice, and the leaves are complete answers. Seeing it that way is the difference between memorising a template and being able to derive one, because every question you have (how deep, how many, where do I prune) is a question about that tree.
Ask what one CHOICE looks like at each step and the tree defines itself. For permutations of n items, the root has n branches for which item goes first, each of those has n-1 branches, and the leaves at depth n are the n! orderings. For subsets, every element gives a binary choice of in or out, so the tree is depth n with 2 branches per node and 2^n leaves. Nothing is allocated: the tree exists only as the shape of your recursion, and the path from the root to where you currently are is exactly the partial answer you are holding. That correspondence is the whole mental model, and once you have it, the code is a transcription.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles