How does subset-sum decide whether valued items split into two equal-value halves?

## The problem An estate holds `n` indivisible items, each with an integer appraised amount. Two heirs must receive equal total value, and no item can be cut in half. Deciding whether such a split exists is the equal-partition question, and it is subset-sum wearing a different hat. ## The reduction, in two moves **Move one: fix the target.** If the two halves must be equal, each is worth exactly `total / 2`. So an odd total is an immediate no — two integers that sum to an odd number cannot be equal. This parity check costs one pass and saves the entire table when it fires; interviewers notice when it is missing. **Move two: search one side only.** You never need to construct both halves. Any subset summing to `total / 2` forces its complement to sum to the same amount, so the whole question reduces to: *is `total / 2` reachable as a subset sum?* ## From value maximisation to reachability The knapsack skeleton is choose-or-skip under a budget. Here each item's amount is simultaneously what it costs (it consumes budget) and what it is worth (it contributes to the sum). When cost and worth are the same number, maximising value under a budget of `target` degenerates: the best you could ever do is exactly fill the budget. So instead of storing "best value so far", the cell stores a single bit: `reach[s]` = true if some subset of the items processed so far sums to exactly `s`. The base case is `reach[0] = true`: the empty selection reaches zero. Getting this wrong is fatal in a quiet way — start with every cell false and no cell ever becomes true, because each update reads an earlier cell. Everything else starts false. Processing an item of amount `a` marks newly reachable sums: `s` becomes reachable if `s - a` was already reachable without this item. The answer is `reach[target]` after all items. Note the boolean form still owes the same debt as the value form: each item may be used only once, so the update must read the state from *before* the item was offered. ## Cost, and what the cost is measured in There are `n` items and `target + 1` cells, so O(n · total/2) updates and O(total) memory in the flattened form. The second factor is a **money magnitude**, not a count of inputs — ten items appraised in whole currency units are cheap; ten items appraised to the cent in the millions are not. A boolean table is the cheapest possible cell, and packing bits makes the memory small even for large targets, but the time is still proportional to the target. ## Variants that ride on the same table - **Report the split, not just its existence.** Keep the two-dimensional table (or a parent-pointer trail) and walk back from `(n, target)`: if the cell was already true without item `i`, skip it; otherwise assign item `i` to the first heir and move to `target - amount[i]`. - **As even as possible.** If no exact halving exists — which is the common real-world case — find the largest reachable `s <= total / 2`. The best achievable difference is `total - 2s`, and that single scan of the finished row answers the practical question the heirs actually have. - **Count the splits.** Replace the boolean with an integer count and the OR with addition, and the table reports how many subsets hit the target. Each unordered split is then counted twice, once from each side. ## Assumptions worth stating out loud The table is indexed by sums, so amounts must be **non-negative integers**. Negative amounts (a debt attached to an item) break the monotone budget framing and need the whole range shifted by an offset before indexing. Amounts of zero are harmless but make the split non-unique. Items must be indivisible — that is what forces the yes/no decision per item rather than a proportional one. ## The wrong answers to avoid - "You have to try all 2^n subsets." Only if you refuse to reuse sub-answers; two different subsets reaching the same running sum are interchangeable from that point on, which is exactly what the table exploits. - "Both halves need the same number of items." Equal value, not equal count — three small items can balance one large one. - "The cell holds how many items were used." It holds one bit of reachability; conflating the two produces a table that answers a question nobody asked.