Why taking the largest lot fails
Suppose a fictional allocation must total exactly 7 units. Three distinct lots are available in sizes 6, 4 and 3 units. Each lot can be taken whole or skipped, and each can be used at most once.
Try taking the 6-unit lot first. Taking 4 as well brings the total to 10, so the search cuts off that branch before deciding about the 3-unit lot. It undoes the choice to take 4 and tries skipping it. Taking 3 then brings the total to 9, while skipping 3 leaves 6 with no lots left. Both fail. Now undo the choice to take 6. From a total of 0, skip 6, take 4 and take 3. The search reaches 7. Of the eight possible subsets, only the lots of 4 and 3 units meet the target.
A pruning rule needs a proof
The overshoot rule works because every remaining lot has positive size. The total can only stay the same or rise, so a subtotal above 7 can never come back down to 7. With signed adjustments, taking 6 and 4 would still reach 10, but a later adjustment of −3 could bring it back to 7. Pruning at 10 would then throw away a feasible result.
Search state and the cost of finding an answer
append makes an include choice and pop restores the shared list before the alternative is tried. The running total is local to each call, so the parent already has its earlier total. The first match is copied before unwinding. Unlike a depth-first traversal of a given graph, this search generates its own states from the choices and can discard all completions of a partial state with a feasibility test.def exact_allocation(lots: tuple[int, ...], target: int) -> list[int] | None:
"""Find one exact allocation using each positive integer lot at most once."""
chosen: list[int] = []
def search(index: int, total: int) -> list[int] | None:
if total == target:
return chosen.copy()
if total > target or index == len(lots):
return None
lot = lots[index]
chosen.append(lot)
result = search(index + 1, total + lot)
chosen.pop()
if result is not None:
return result
return search(index + 1, total)
return search(0, 0)
print(exact_allocation((6, 4, 3), 7))
# [4, 3]Each of lots creates two choices, so the unpruned tree has complete allocations. The code uses only overshoot pruning. If the target exceeds the sum of all lots, neither success nor overshoot occurs, and the code visits every branch. The worst-case time is under constant-time updates to the index and total. A failed branch only rules out completions of its own choices. Reporting infeasibility requires ruling out every branch, either by reaching the end or by proving it can be pruned.
Sources
- Jeff Erickson, Algorithms, Chapter 2, §2.3 and §2.4 on subset sum, include-or-exclude recursion and the size of the search tree.
- Stanford CS106B, Recursion and Iteration, Backtracking, Problem Seven on deciding feasibility and returning one selected subset.