In backtracking, when is copying the state into each call better than mutating and undoing?
answer
- who pays for the safety here
- how big is the thing being copied
- cost per node times number of nodes
- copies stay alive down the whole depth
- scalars are already copies
basics
~20 sCopy when the state is small or the recursion shallow, buying safety with the constant factor. Copying costs the state's size at every node and one live copy per level; mutate-and-undo costs little but demands a restore on every exit.
solid answer
~50 sNeither choice changes how many nodes the search visits — that is set by the branching and the pruning, and stays exponential either way. What changes is the per-node constant and the memory profile. Copying multiplies the work at each node by the size of the state and holds one copy per active level, so peak memory is roughly state size times depth; in exchange, every exit path is automatically clean, which removes the entire forgotten-restore bug class. Mutate-and-undo keeps a single shared structure and pays only the depth of the recursion, but the correctness burden moves to the reviewer. The honest answer to a skeptic who says "just copy, it's safer" is: agree for scalars and small state, and refuse for bulky state — a running total is copied for free, a large occupancy grid is not.
go deeper
Know that a value passed down as a parameter restores itself when the call returns, while a shared structure the call edits does not — that difference is the whole choice.
Quantify both sides: copying costs the size of the state at every node and holds one copy per level; mutating costs one shared structure plus the discipline of restoring on every exit.
Argue the hybrid and defend it with numbers — state size, expected node count, their product — and name how you enforce the restore invariant for whatever you chose to mutate.
Own the maintenance dimension: which discipline survives the fourth engineer adding the fifth pruning guard, and whether a constant-factor cost is a fair price for deleting an entire class of silent bugs.
## What is actually being traded A backtracking call carries state: the partial selection, a running aggregate, sometimes an occupancy map or a set of used resources. There are two disciplines for moving that state down the tree. **Mutate and undo.** One shared structure. Each call changes it, recurses, and changes it back. Extra space is whatever the recursion itself needs — `O(depth)` frames plus one copy of the state, total. Extra time per node is `O(1)` for a scalar or a push/pop. **Copy down.** Each call receives its own snapshot and never touches its parent's. Extra time per node is `O(|state|)` for the copy. Peak extra space is `O(|state| × depth)`, because every call on the current root-to-node path is holding its own snapshot alive simultaneously. Notice what is *not* in that list. The number of nodes explored is identical under both disciplines: it is a property of the branching factor and the pruning, not of how state travels. Copying does not make an exponential search polynomial, and undoing does not make it faster asymptotically. This is a **constant-factor and memory** decision, and it should be argued as one. ## The numbers that decide it Multiply the per-node copy cost by the node count. For a bundle builder over a gift catalogue, the state might be: | State | Copy cost per node | Verdict | | --- | --- | --- | | Running total in cents | `O(1)` | Copy — it is a value; passing it as a parameter *is* the copy | | Selection of `k` chosen indices | `O(k)`, up to `O(n)` deep in the tree | Judgement call; copying multiplies total work by up to `n` | | Per-supplier remaining-stock table | `O(m)` for `m` suppliers | Copy only if `m` is genuinely small | | Large occupancy grid | `O(cells)` | Mutate and undo; copying is prohibitive | The rule of thumb that falls out: **pass scalars by value and mutate only the bulky structures.** Most real backtrackers are hybrids, and the hybrid is not a compromise — it is the correct answer. There is no virtue in mutating a single integer, and no virtue in snapshotting a grid. ## The safety argument, taken seriously The skeptic's case for copying is strong and it is about *exit paths*, not aesthetics. With mutate-and-undo, correctness depends on an invariant a human must maintain: every return restores what the call changed. Pruning guards, availability checks, error paths and early successes are all returns, and each is a place the restore can be forgotten. Copying makes the invariant hold by construction — a call that abandons its own snapshot cannot damage anyone else's. That matters more as the code ages. The original author holds the invariant in their head; the person adding the fourth pruning condition eighteen months later does not. If the search is on a path where a silently-short result set would go unnoticed, and the state is small, paying a constant factor to delete a whole bug class is a good trade — and saying so is the senior answer, not a concession. ## When copying is the wrong instinct Three cases where you should push back: 1. **Bulky state.** Snapshotting a large structure at every node can dominate the search entirely, turning a fast exponential walk into a slow one and pushing peak memory to state size times depth. The search that used to fit now allocates on every node. 2. **Deep recursion.** Depth multiplies the live snapshots. A deep search with medium state is the worst combination: many copies, all alive at once. 3. **State that is expensive to copy but cheap to reverse.** An incremental aggregate — a running sum, a count per category, an occupancy bitmask — is often `O(1)` to apply and `O(1)` to reverse, while a faithful copy is linear. Reversibility is the property to look for, and when it is there, undoing is not merely faster, it is simpler. ## How to defend the choice Make the argument concrete rather than stylistic: state the size of the state, the node count you expect on realistic input, and the product. Then name the mitigation for whichever risk you accepted — if you mutate, say how the restore invariant is enforced (single exit point, or a post-condition assertion in tests that the state is back to its initial value after the top-level call); if you copy, say what bounds the state size so the constant cannot grow silently. Mainstream runtimes differ here in ways that shift the constant but not the argument: some make a small immutable snapshot nearly free while others make every copy an allocation, so the crossover point is measured on your platform, not assumed.
- Does copying change the asymptotic complexity of the search?Not the node count, which is what dominates: the branching and pruning decide that, and it stays exponential. Copying multiplies the work at each node by the size of the state, so the total gains a factor of the state size, and peak extra memory becomes state size times recursion depth instead of a single shared structure. It is a constant-factor and memory change, argued in those terms.
- What property of the state makes mutate-and-undo clearly the right choice?Cheap reversibility. If applying a choice and reversing it are both constant-time — adding then subtracting a price, setting then clearing a flag, incrementing then decrementing a counter — undoing costs nothing while a faithful copy is linear in the state. Look for that asymmetry first; when it is present, mutating is both faster and simpler to read than snapshotting.
- How do you keep the mutate-and-undo invariant honest as the code grows?Enforce it mechanically rather than by discipline. Funnel exits through one restore point so a new guard cannot bypass it, and add a test asserting the shared state equals its initial value after the top-level call returns. That post-condition fails on the first forgotten restore, regardless of which branch introduced it, and it costs one assertion.
Mutating with an undo is one whiteboard and a strict eraser discipline; copying is handing every visitor their own photocopy. The photocopies never conflict, but you pay for the paper at every desk and you carry the whole stack while you are still walking.
saying these in an interview costs you the question
- Claims copying makes the search asymptotically slower by an exponential factor
- Ignores that copies of every level are alive at once
- Says mutate-and-undo is always faster, whatever the state
- Treats it as a style preference rather than a measured tradeoff
- Copies a scalar and mutates a large structure, exactly backwards