The Backtracking Template

Some problems cannot be solved by a single clever formula - they require systematically trying every reasonable possibility until you find the ones that work. Generating every subset of a list, every ordering of a list, every valid placement of pieces on a board: all of these are "search" problems, and all of them share the same underlying shape. That shape is called backtracking, and once you have seen the template once, you will recognize it everywhere.

Backtracking builds up a candidate solution one decision at a time, using recursion to explore what happens after each decision, and then undoing that decision before trying the next one. Every backtracking function follows the same three moves at each step:

• -Choose - add one option to the current partial solution (append to a list, mark something as used, place a piece on a board).
• -Explore - recurse, so the rest of the algorithm runs as if that choice were permanent.
• -Un-choose - undo exactly what was chosen (pop from the list, unmark it as used, remove the piece), so the next sibling option starts from a clean slate.

The "un-choose" step is what makes backtracking distinct from plain recursion. Without it, the single `path` list would just keep growing across every branch of the recursion tree, mixing choices from unrelated branches together. Popping the last choice after the recursive call returns resets `path` to exactly what it looked like before that choice was made, so the next iteration of the loop is free to try a different option from the same clean starting point - one list, reused safely across every branch, instead of a fresh copy at every level.

The clearest first example is generating every subset of `[1, 2, 3]`. At each position, there is a simple choice: include the next number, or do not. Recording `path` at every step of the recursion (not just at the end) captures every subset, because every prefix along the way is itself a valid subset.

Walking through it by hand: the call starts with `path = []`, which is recorded immediately as the empty subset. Choosing `1` gives `path = [1]`, recorded, then choosing `2` gives `[1, 2]`, recorded, then `3` gives `[1, 2, 3]`, recorded. That branch has no more numbers to try, so it pops back to `[1, 2]`, then to `[1]` - where the loop moves on to try `3` next (skipping `2`, since `start` advanced past it), giving `[1, 3]`. Eventually the whole first branch pops all the way back to `[]`, and the outer loop starts over with `2` as the first choice, then `3`. Every one of the 2³ = 8 possible subsets gets recorded exactly once, in the order shown above.