Exercise 2: Why a Negative Item Breaks the Pruning Rule — Possible Solution ==================================================================== WHY THE PRUNE CONDITION SPECIFICALLY DEPENDS ON ALL-POSITIVE ITEMS ------------------------------ This chapter's own pruning rule, "if current_sum > target, stop immediately," is only correct because every remaining item can only ever ADD to the current sum (since all items are positive) - once the sum has overshot the target, there is truly no way for any of the positive numbers still available to bring it back down. If even one item in the list can be negative, this guarantee no longer holds: adding a later negative item could bring an over-target sum back down to exactly the target, meaning current_sum > target no longer proves the branch is hopeless. A CONCRETE VERIFIED EXAMPLE ------------------------------ Using items = [40, -10, 5] with target = 35: the true sum of all three items is exactly 35, so [40, -10, 5] genuinely is a valid answer. Running the chapter's own unmodified backtracking algorithm on this list, however, returns no answer at all (found = None), even though a valid one exists. This happens because the algorithm includes 40 first, reaching a running sum of 40, which is already greater than the target of 35 - the flawed prune condition fires immediately and the branch is abandoned, so the algorithm never even considers including -10 next (which would have brought the running sum back down to 30, setting up the final +5 to reach exactly 35). WHY THIS IS A GENUINE MISS, NOT JUST INEFFICIENCY ------------------------------ This is a more serious problem than the earlier chapters' own efficiency concerns (like Chapter 6's slow brute force) - an inefficient algorithm still eventually finds the correct answer, just slowly. This flawed pruning rule applied to items containing negative numbers doesn't just search a smaller space - it can PERMANENTLY eliminate the only path that would have led to the correct answer, producing a wrong result (falsely reporting no solution exists) while still running quickly. A correct version of this algorithm would need either a different pruning rule that accounts for the smallest possible remaining values (which could be negative), or no early-exit pruning at all when negative values are possible. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation identifies precisely why the pruning rule's own justification depends on the all-positive assumption, and backs the claim with an actual constructed example run through the chapter's own unmodified algorithm, confirming it genuinely fails to find a demonstrably valid answer - not just a hypothetical worry, but a verified, real failure.