In backtracking, which values belong in call parameters versus the shared path?

## Two kinds of state, one distinguishing question Every backtracking routine carries state, and the useful way to classify it is: **who puts it back?** - **Call-private state** lives in the parameters and locals of a single invocation. The recursive call receives its own copy; when it returns, the caller's copy is exactly as it was. The call stack restores it, at no cost in code. - **Shared state** lives in one structure that every depth reaches. Nothing restores it on return, so each write must be matched by an explicit undo after the recursive call — the un-choose step. The roster search makes the split concrete. The **slot index** is call-private: the call handling slot 3 recurses with 4 and, when that returns, still holds 3 without anyone writing a line. The **partial roster** is shared: it is deliberately one structure so that descending a level costs a single write instead of a full copy, and the price of that choice is the explicit undo. ## What happens when you get it backwards **Index promoted to shared state.** The fragment above works — but look at what it costs. The loop now performs two state changes and two restores per candidate instead of one. Worse, the restore of the index has to happen *before* the path is cleared, since clearing uses the index; an ordering constraint has appeared where none existed. Every piece of state you move out of the parameters is one more thing that has to be put back in the right order. **Arrangement handed out by copy.** Give each call its own copy of the partial roster and un-choose disappears entirely — the design is correct and, for small depths, genuinely simpler. The bill arrives at scale: you copy at every **node** of the decision tree, whereas the shared-path design copies only at **leaves**, and only when the caller wants the arrangements materialised. Internal nodes vastly outnumber leaves in a wide tree, so this is the difference between paying `O(depth)` per node explored and paying it per solution emitted. ## A practical rule Ask of each value: *does the next level see a different value, and does the current level need its own back afterwards?* - Different per level, needed back afterwards, cheap to copy — **parameter**. Position, depth, remaining budget as a number, the index a loop starts from. - Shared by all levels, expensive to copy, mutated incrementally — **shared state with an explicit undo**. The partial arrangement, occupancy or availability markers, running aggregates over the path. - Never changes at all — neither. The candidate sets, the target size, the input itself: hoist them out and read them, rather than threading them through every frame or shadowing them in mutable state. That last category matters more than candidates expect. Threading the immutable input through as a parameter at every level is harmless but noisy; the real defect is copying it, which quietly turns an `O(1)` descent into an `O(n)` one. ## Recursion depth is space One more consequence of putting state in parameters: parameters are stack. A backtracking routine's space is one frame per level plus the shared structures, so `O(d)` where `d` is the depth — as long as what each frame holds is small. Widen the frame with a copied structure and the space becomes `O(d)` copies, i.e. depth times the size of the thing copied. The shared-path design is precisely the trade that keeps auxiliary space at `O(d)` in total rather than `O(d)` structures. ## Saying it in an interview A compact answer: *"Position-like state goes in parameters because the stack restores it for me; the arrangement and any markers shared across levels go in one structure, and every write to that structure gets a matching undo after the recursive call. If I copied the arrangement per call I would not need the undo, but I would pay a copy at every node instead of at every solution."* That sentence covers the design, the reason and the trade, and it is what the interviewer is listening for.