In backtracking, why must you un-choose after the recursive call returns?

## The model: a decision tree that is never stored Backtracking attacks problems that ask for *arrangements*: fill every slot with some candidate such that a set of rules holds. A useful running example is a weekly shift roster — a fixed sequence of shift slots, and for each slot a set of workers eligible to cover it. The search space is a tree. The root is "nothing decided yet". Level 1 branches over the candidates for the first slot; under each of those, level 2 branches over the candidates for the second slot; a leaf at depth `n` is one complete roster. The critical property is that this tree is **implicit**. It is never built in memory. At any instant the algorithm is standing on exactly one root-to-current-node path, and the recursion stack *is* the record of where it stands. That is why the memory cost of a backtracking search is proportional to the depth of the tree, not to its (usually exponential) size. ## Why one shared path, and what that forces The partial arrangement — the choices made so far — has to live somewhere. Two designs are possible. One is to pass a fresh copy of the partial arrangement into every recursive call. This is correct and needs no un-choose at all: each call owns its own snapshot, and when it returns, its snapshot is simply discarded. The price is a copy at every node of the tree, which multiplies the cost of the search by the depth and allocates once per node explored — and nodes explored is the exponential quantity. The other design, the one the standard template uses, is a **single shared path structure** that every depth writes into. Now no copying happens on the way down, but the structure is no longer private to a call. It carries mutations made by the subtree that just finished. Un-choose is the payment for that: after `explore` returns, the caller removes the choice it made so the shared structure is restored to what its own caller handed it. So the three steps are not decoration: - **choose** — write this candidate into the path at the current position; - **explore** — recurse to the next position; the subtree beneath this choice is examined completely; - **un-choose** — remove the write, so the shared path is exactly as it was on entry. ## The invariant, stated precisely > On entry to and on return from the call handling depth `k`, the path holds exactly `k` choices — the ones made by the ancestors of this node. Every correctness argument about the template reduces to this. It is also the sentence to say out loud in an interview, because it explains *both* siblings and ancestors at once: siblings each begin from the same clean prefix, and the caller can keep looping without knowing anything about what the subtree did. ## What goes wrong without it Drop the un-choose from the roster search and the second candidate for slot 1 begins with the entire path left over from the first candidate's deepest branch. The search then reports rosters that assign several workers to one slot, or reaches the "all slots filled" base case at the wrong depth, or misses whole regions of the space because the path never shrinks. The bug is nasty in practice precisely because the *first* solution found is usually correct — the corruption only appears once the search has come back up out of a subtree for the first time. ## "Isn't this just brute force?" Brute force in the naive sense builds each complete candidate from scratch and tests it. The template shares work: everything computed for a prefix is computed once and reused by every leaf under that prefix, and the arrangement is grown and shrunk incrementally rather than rebuilt. What the template does **not** do is change the asymptotics on its own — the number of leaves is still exponential in the number of slots. It is a disciplined, memory-cheap way to enumerate that space, not a way to shrink it. ## Traversal order Because each call fully explores a candidate's subtree before trying the next candidate, the enumeration is depth-first, and solutions come out in the order the candidate loops impose. If the candidates for each slot are considered in a fixed order, the leaves are produced in the lexicographic order of the choice sequences — which is why backtracking output tends to look sorted even though nothing sorts it.