Why must a backtracking collector copy the path before recording a solution?
answer
- Stored: a handle or a picture?
- Only one path exists during the whole search
- Replay the un-choose steps after the last leaf
- All entries read empty at the end
- Snapshot at the leaf, cost O(depth) each
basics
~20 sThe path is one shared structure that keeps mutating. Recording it directly stores a reference, not a snapshot, so every recorded solution aliases the same structure and ends up showing its final, fully undone contents.
solid answer
~50 sIn the standard template the partial answer lives in a single structure that every depth writes into and the un-choose step later clears. Recording that structure at a leaf stores a *reference* to it, so the collection fills with the same object repeatedly; as the search continues it keeps changing underneath the results, and when the search finishes and everything has been un-chosen, every stored entry reads as empty or as the last arrangement visited. The fix is a snapshot: copy the path's current contents into a fresh structure at the leaf, and record the copy. That costs `O(depth)` time and memory *per solution emitted*, which is the price of materialising output and is unrelated to the cost of the search itself. If the caller only needs how many solutions exist, skip the copy and increment a counter.
code
pseudocode · 13 linespath = array of size num_slots, all EMPTY
results = empty collection
solve(slot):
if slot == num_slots:
add(results, path) // records the shared array itself
return
for each worker in eligible(slot):
path[slot] = worker // choose
solve(slot + 1) // explore
path[slot] = EMPTY // un-choose
solve(0)go deeper
Recognise the symptom: the search finds the right number of answers but every stored answer looks identical or blank. Learn to spot the recording line that stores the live structure instead of a snapshot.
Explain the aliasing mechanically — one structure, many handles, mutation continuing after the record — and state the copy's cost as per-solution rather than per-node.
Show judgment about how deep the snapshot must be when the path carries mutable records, and defend copying at leaves only rather than making the state private at every call.
Frame it as an interface decision: whether the routine returns all arrangements, a count, or an aggregate determines the memory profile far more than anything inside the loop.
## The defect in one sentence The template deliberately keeps **one** partial answer alive and mutates it in place. A collector that records that structure records a handle to the live thing, not a picture of it — so the collection is a pile of aliases to a structure that is still being edited. ## Tracing what actually ends up in the results Take the roster search: slots along the week, eligible workers per slot. Suppose there are three complete rosters. The search descends to the first leaf, records the shared path, and returns. On the way back up, each level runs its un-choose, so the shared path shrinks. It then descends to the second leaf and records the *same* structure again. And so on. When the top-level call finally returns, every choice ever made has been undone — that is exactly what the invariant promises. The results collection now holds three entries, all pointing at one array, and that array is empty. The output is three identical blank rosters. A variation on the same bug (when the outermost loop's last un-choose is skipped, or when the collection is inspected mid-search) shows every entry as the *last* arrangement visited. Both symptoms have one cause. This is a reviewer-visible defect: `add(results, path)` with no copy is a line a code reviewer can flag without running anything, and interviewers plant it deliberately in read-the-fragment questions. ## The fix and its exact price Record `copy(path)` — a fresh structure holding the current contents. Now the entry is a snapshot; later mutation of the shared path cannot reach it. The cost is `O(d)` time and `O(d)` extra memory for each solution emitted, where `d` is the depth (the number of slots). Two things about that cost matter in an interview: 1. **It is charged per solution, not per node.** The search visits far more internal nodes than leaves; copying at leaves only is why the shared-path design is worth having in the first place. Copying at every node — the alternative that would make un-choose unnecessary — pays `O(d)` at every node explored instead. 2. **It is output cost, not search cost.** Total time becomes `O(nodes explored + d x solutions)`. If a problem has an exponential number of solutions, the copy is not what makes it expensive; producing the answer at all is. ## Shallow versus deep snapshots A copy is only as safe as it is deep. If the path holds plain values — worker identifiers, indices, characters — a flat copy of the container is a genuine snapshot. If the path holds records that the search itself mutates (say, a shift record whose assigned-hours field is updated as choices are made), then a flat copy still shares those records, and the same aliasing bug reappears one level down. The rule to state is: a snapshot must be deep enough to cover everything the search mutates, and no deeper. ## Collecting versus counting The copy exists only because the caller wants the arrangements themselves. Three common shapes, each with a different cost: | What the caller needs | At the leaf | Extra memory | |---|---|---| | All arrangements | copy the path, record the copy | `O(d x solutions)` | | How many arrangements | increment a counter | `O(1)` | | An aggregate (best, cheapest, a sample) | score the live path, keep the winner | `O(d)` | Notice that only the first shape ever needs a copy, and even the third needs just one retained snapshot rather than one per solution. Deciding which shape the caller actually wants is the single biggest lever on the memory profile of a backtracking routine — bigger than any micro-optimisation inside the loop. ## Why juniors and mid-level candidates trip here The symptom is confusing: the algorithm is *right*, the search order is right, the count is right, and the output is garbage. Candidates who have only ever written the template with immutable strings or with copy-per-call state have never met the bug, because concatenating characters onto an immutable value produces a new value at each level and there is nothing to alias. Move the same code to a mutable container for efficiency and the bug appears — which is why "what changes if the path is a mutable structure?" is such a common interview follow-up.
- How much does the copying add to the routine's total complexity?`O(d)` time and memory per emitted solution, where `d` is the depth, so total time is roughly the nodes explored plus depth times the number of solutions. It is output cost, charged only at leaves — unlike the copy-per-call alternative, which pays `O(d)` at every node visited. When solutions are exponential in number, materialising them dominates, not the copying constant.
- When is a flat copy of the path not enough?When the path holds records that the search itself mutates rather than plain values. A flat copy duplicates the container but shares those records, so later mutation still leaks into every recorded snapshot. The snapshot must be deep enough to cover every field the search writes to, and no deeper — copying immutable payloads is wasted work.
- If the caller only wants the number of valid rosters, what changes at the leaf?Nothing is copied and nothing is stored: increment a counter and return. Extra memory for output drops from depth times solutions to constant, and the per-solution `O(d)` copy disappears. The traversal, including choose and un-choose, is unchanged — the number of leaves reached is the same, so total time stays proportional to nodes explored.
It is like photographing a whiteboard by writing its location on a sticky note. Come back later and the board has been wiped — every note points at the same blank board.
saying these in an interview costs you the question
- Says recording the path directly is fine because recursion copies it
- Blames the un-choose step for the empty results
- Claims the copy changes the search's asymptotic complexity
- Assumes a flat copy is always a real snapshot
- Copies at every node instead of only at leaves