A lesson from the Algorithms & Patterns module of the bootcamp. About a 12 minute read.
Backtracking is depth-first search over a tree of decisions that you never actually 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 memorizing 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 is a yes-or-no choice, in or out, so the tree is n deep 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 are right now is exactly the partial answer you are holding. That is the whole mental model, and once you have it, the code is just a transcription.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles