Why prune a backtracking branch as soon as the running total exceeds the budget rather than at the leaf?
answer
- picture the search as a decision tree
- what does one return statement delete
- everything below the current node
- can later items ever lower the total
- non-negative prices means totals only grow
basics
~20 sTesting only at the leaf still walks every branch to the bottom. Testing on entry deletes a whole subtree in one return: once the running total is over budget, more items can never bring it back down.
solid answer
~50 sA backtracking search is a depth-first walk over a decision tree: at each item you take it or skip it, so there are roughly `2^n` leaves. If the budget is only checked at the leaf, you build every one of those bundles and throw most of them away. Checking on entry turns one `return` into the deletion of an entire subtree — prune at depth `d` and you skip about `2^(n-d)` leaves for free. The prune is only sound because prices are non-negative, which makes the running total monotonically non-decreasing as you descend: no descendant can undo the overrun. That is the general shape of pruning — a cheap bound proving no descendant can be a solution. Measure the win as nodes visited, not wall-clock: the saving is entirely data-dependent, and the worst case is still exponential.
code
pseudocode · 12 lines// prices[] and budget are in whole cents
build(i, total, chosen):
if i == length(prices):
if total <= budget:
record(chosen)
return
// skip item i
build(i + 1, total, chosen)
// take item i
push(chosen, i)
build(i + 1, total + prices[i], chosen)
pop(chosen)go deeper
Be ready to say that a return at the top of a recursive call skips an entire subtree, not one candidate, and that adding more non-negative prices can never bring an over-budget total back down.
Explain the prune as a bound: a cheap test proving no descendant can be feasible. Show you know the monotonicity assumption it rests on and what breaks when a price can be negative.
Demonstrate that you measure the win in nodes visited across different catalogue shapes, and that you weigh the per-node cost of the check against the subtrees it actually removes.
Own the framing that pruning buys average-case speed and a smaller constant, never a better worst case, and that anything shipped on this search still needs an input bound or a work cap.
## The search as a tree Picture a bundle builder over a catalogue of gift items, each with a price in whole cents, and a spending cap. The natural backtracking formulation walks the items in order and, at item `i`, branches twice: **take it** or **skip it**. Every recursive call is a node of a binary decision tree; every root-to-leaf path is one candidate bundle. With `n` items there are `2^n` leaves and roughly `2^(n+1) - 1` nodes. That tree is the unit of cost. Anything you say about "how fast the search is" is really a claim about how many of its nodes you touch. ## Checking at the leaf: generate, then filter The first version everyone writes recurses all the way down and tests `total <= budget` at the bottom: ``` if i == length(prices): if total <= budget: record(chosen) return ``` This is correct and useless. The test's result has no influence on the search — the walk visits every node no matter how tight the cap is. A cap of one cent costs exactly as much as a cap of a million. ## Checking on entry: deleting subtrees Move the constraint to the top of the call: ``` if total > budget: return ``` Now the `return` does not skip one candidate; it skips **everything below the current node**. Prune at depth `d` and you avoid roughly `2^(n-d)` leaves in a single step. Pruning near the root is worth exponentially more than pruning near the bottom, which is why ordering heuristics (consider the expensive items first, so the total crosses the cap early) compound with pruning rather than merely adding to it. ## Why the prune is allowed at all The prune is sound only because of **monotonicity**: prices are non-negative, so the running total never decreases as you descend. If the prefix already violates the constraint, no extension can repair it. State that condition out loud in an interview — it is the actual content of the answer. Break the condition and the prune silently loses answers. Add a promotional item with a negative price (a credit that reduces the bill) and a prefix that is over budget today can come back under later. The sound version then prunes against a *bound* rather than the raw total: compare `total + (sum of the remaining negative prices)` against the budget, which is the best any descendant could achieve. Generalised: **prune when a cheap, provably optimistic bound shows no descendant can be feasible** — never merely because the current partial state looks bad. ## What pruning is worth, and what it is not worth The saving is entirely data-dependent: | Catalogue shape | Effect of the entry check | | --- | --- | | Most items priced near the cap | The total crosses within a couple of levels; huge subtrees vanish | | Many items priced far below a generous cap | Almost nothing is ever over budget; the full tree is walked | So the honest report is a **node count**, not a stopwatch: instrument the recursion, count calls with and without the check on the same catalogue, and quote the ratio. Wall-clock numbers on one laptop conflate the prune with cache effects and warm-up. Two further cautions. First, the check is paid at *every* node, so it must be cheap relative to the subtree it removes; an expensive feasibility computation at each node can cost more than the branches it saves. Second, pruning does not change the asymptotic worst case. Big-O is an upper bound over all inputs, and the input above (many cheap items, generous cap) still forces the full `2^n` walk. A pruned search is a faster exponential search, not a polynomial one. ## Where it puts you next One practical consequence worth internalising early: the entry check introduces a **second exit path** from the recursive call. Any state the call has already mutated must be restored on that path too — the pruning `return` is exactly the line that forgotten-restore bugs hide behind.
- Suppose the catalogue can contain a promotional item with a negative price. What happens to the prune?It becomes unsound. The running total is no longer monotone, so a prefix that is over budget now can come back under once the credit is taken, and the prune throws away real answers. The fix is to prune against an optimistic bound instead: compare the running total plus the sum of all remaining negative prices — the lowest any descendant could reach — against the budget.
- How would you demonstrate that the pruning actually helped?Count recursive calls, not milliseconds. Run both versions over the same catalogues, report nodes visited and the ratio, and vary the input shape — a cap near the total catalogue price prunes almost nothing, a tight cap prunes near the root. Wall-clock timing on one machine mixes in warm-up and memory effects and hides that the saving is a property of the data.
- Does it matter whether the check sits at the top of the call or just before each recursive call?Not asymptotically — both delete the same subtrees. Testing before each call saves one call frame per pruned branch; testing on entry states the invariant in a single place, which is easier to keep correct as more constraints are added. The entry form is the safer default, provided every mutation made before that return is restored.
It is the difference between reading every page of every book in a wing and reading the sign on the wing's door. Once the sign says the wing is over your price range, you skip every room inside it at once.
saying these in an interview costs you the question
- Claims pruning makes the search polynomial
- Cannot say why the prune loses no valid bundles
- Ignores that non-negative prices are what make it sound
- Measures the improvement only in milliseconds, never in nodes
- Thinks filtering at the leaf and pruning on entry cost the same