A backtracker returns early after the choose step, skipping the un-choose — what breaks downstream?

## The fragment under review A reviewer is looking at a bundle builder that carries its state in shared, ambient variables — a running `total` in cents and a `chosen` path of item indices — rather than passing them down as parameters. Someone has added a stock check, and put it after the choose step: ``` explore(i): if total > budget: return if i == length(prices): record(chosen); return total = total + prices[i] // choose item i push(chosen, i) if not in_stock[i]: return // added later: skip unavailable items explore(i + 1) total = total - prices[i] // un-choose pop(chosen) explore(i + 1) ``` The diff is two lines and reads as obviously safe. It is not. ## What the contract actually is Mutate-and-restore backtracking rests on a single invariant: **when a call returns, the shared state is exactly what it was when the call was entered.** That is what lets a parent make one choice, explore, undo it, and make the next choice on clean state. The invariant is a property of *every* return, not of the last one. A call with three exit paths must restore on three exit paths. The added `return` violates it. On an out-of-stock item, the call leaves `prices[i]` folded into `total` and index `i` sitting on `chosen`, then hands control back to its parent — which unwinds on the assumption that the child was clean. ## The two symptoms, and they point in opposite directions **False pruning (answers lost).** The inflated `total` makes the entry guard `total > budget` fire on branches that are genuinely affordable. The search reports *fewer* bundles than exist. This is the nastier symptom: nothing crashes, nothing is obviously wrong, and the result set is merely quietly short. **Phantom membership (answers wrong).** The stale index stays on `chosen`, so any bundle recorded further along includes an item the search never actually took — and, since the item is out of stock, one that cannot be sold. There is a third defect hiding in the same two lines: the early return also skips the final `explore(i + 1)`, the *skip-this-item* branch. So an out-of-stock item does not merely fail to be taken; it terminates the exploration of every item after it. The intended behaviour — "treat this item as unavailable and carry on" — is not what the code does at all. ## Why the tests were green The bug needs a coincidence of conditions to be visible: - an out-of-stock item must exist, and - it must be followed by further items (otherwise the polluted state is discarded as the recursion finishes), and - the pollution must matter: the inflated total has to actually cross the cap, or the phantom index has to reach a recorded bundle. A fixture with four items, one out of stock at the end, and a generous cap satisfies none of the last two. Assertions on *counts* are especially weak here, because losing a bundle and gaining a corrupted one can cancel out in a count. Tests that would have caught it: an out-of-stock item early in the catalogue with a cap tight enough to bite; an assertion that the shared state equals its initial value after the top-level call returns; and an assertion on the *contents* of every recorded bundle, not just how many there are. ## The fixes, ranked 1. **Check before you mutate.** Move the stock guard above the `total = total + prices[i]` line — better, fold it into the branch that takes the item, so an unavailable item simply falls through to the skip branch. Nothing is mutated, so nothing needs restoring. This is the structurally correct fix, and it also repairs the skipped-skip-branch defect. 2. **Restore before every return.** Duplicate the two undo lines above the early return. Correct, but it scales badly: the next guard someone adds needs its own copy, and the fourth copy is the one that gets forgotten. 3. **Single exit.** Structure the call so there is one return point after a restore block that always runs. Makes the invariant checkable by reading, at the cost of some nesting. 4. **Stop sharing the state.** Pass the total down as a parameter, which is copied per call and therefore restores itself. This trades a class of bugs for per-node copying cost — the right call for a scalar, a judgement call for a bulky structure. ## The review habit worth stating When you review a backtracker, do not read it top to bottom. Find every `return`, `break`, and error path between a mutation and its undo, and check each one individually. A pruning guard is the most common insertion point precisely because pruning is added later, as an optimisation, to code that already worked.