subset-sum by backtracking

You are given a bag of numbers and a target, and you want to know whether some of them add up to the target exactly. With coins 6, 8, 3 and target 9, the answer is yes (6 + 3). This is the subset-sum problem, and the most direct way to attack it is backtracking: walk through the numbers one at a time, and for each, branch on the binary decision include it in the running sum or skip it.

The state-space tree here is the subset tree: at item i you go two ways, and a node holds the running sum of the items you have included so far plus which item is next. The recursion is, for item i with current sum s: if s equals the target, success; if you have run out of items, fail this branch; otherwise try including item i (recurse with sum s + value[i]) and try skipping it (recurse with sum s). Plain, this visits all 2^n subsets. The whole reason to phrase it as backtracking rather than blind enumeration is the pruning. If all numbers are nonnegative, you can prune two ways: once the running sum exceeds the target, no further inclusion can help, so stop (overshoot pruning); and if the running sum plus the total of all remaining items is still below the target, this branch can never reach it, so stop (under-reach pruning). Sorting the items lets these bounds bite earlier.

Subset-sum matters as the gateway to NP-completeness (it is NP-complete, and a cousin of the partition and 0/1 knapsack problems) and as a clean place to feel how pruning changes everything. Worst case the backtracking is still O(2^n) — for example all items zero and a zero target, where every subset is a solution, so neither prune ever fires and you visit all 2^n. But on many real instances the two bounds slash the tree, and for moderate n a different idea, meet-in-the-middle, lowers the exponent to roughly 2^(n/2), a huge practical win over the naive 2^n.