Partition Equal Subset Sum: Why the Loop Runs Backwards

A loop direction can change what an algorithm is allowed to do. That's the detail I want to make visible in Partition Equal Subset Sum. The final code looks like a modest boolean table, but running one loop forwards quietly gives every input item an unlimited supply of identical friends.
The official LeetCode problem asks whether a list of positive integers can be divided into two groups with equal sums. Each occurrence belongs to exactly one group. Equal values at different positions are separate available items; we aren't partitioning a set of distinct numbers.
The useful move is to stop trying to build both groups simultaneously. Once one group reaches half the total, everything left over necessarily forms the other half. We can ask a smaller question and let arithmetic do the rest.
Turn Two Groups into One Target
Suppose the total is T. Equal groups would each sum to T / 2, so an odd total makes success impossible. That's a valid early exit, not a heuristic: integer group sums cannot equal a half‑integer.
For an even total, we're looking for a subset with sum target = T / 2. Because every input is positive, a partial sum above that target can't become useful by adding later values. That lets us keep a finite table from zero through the target.
Take 2, 3, 5, 6. The total is 16, and we need 8. We could choose 2 + 6 or 3 + 5; either choice leaves another group summing to eight. We don't need to count those possibilities or return their members, just establish that at least one exists.
By contrast, 2, 2, 3, 5 has an even total of 12 but no subset summing to 6. An even total is necessary, not sufficient. I keep that distinction explicit because an early rejection test can look suspiciously like a complete solution when the examples are being helpful.
Describe What Has Been Processed
Let reachable[s] mean that some subset of the items processed so far has sum s. Before seeing any items, only zero is reachable, using the empty subset. We therefore set reachable[0] to true and every other cell to false.
When we encounter a value v, a sum s is reachable if it was already reachable without this item, or if s - v was reachable before processing this item. The second option appends this particular occurrence of v exactly once.
In a two‑dimensional table, we'd read both options from the previous row and write to a new row. That separation makes the item limit obvious. We can reuse one row if we arrange the updates so that the source cell still belongs to the previous row's logical state.
The resulting invariant is worth saying in full: after finishing an item, every true cell represents a subset of the items seen so far, with each occurrence used at most once. The implementation has to preserve that sentence, not merely produce a plausible collection of true values.
Backwards Updates Preserve the Previous Row
For a positive v, the source s - v is smaller than the destination s. If we visit destinations in descending order, that smaller source has not been changed during the current item's pass. It still tells us what was possible before this item arrived.
Forwards iteration does the opposite. Suppose the target is six and the current item is two. It can mark two using zero, then mark four using the newly marked two, then mark six using the newly marked four. One item has been used three times. The code has solved a different problem, very efficiently.
The 2, 2, 3, 5 example exposes that bug. A forwards pass can claim that six is reachable from the first two alone, despite there being no legal partition. Descending iteration prevents this reuse without needing a separate copied array.
For our successful example, the reachable sums up to eight develop like this:
| Items processed | Reachable sums up to eight |
|---|---|
| None | 0 |
| 2 | 0, 2 |
| 2, 3 | 0, 2, 3, 5 |
| 2, 3, 5 | 0, 2, 3, 5, 7, 8 |
| 2, 3, 5, 6 | 0, 2, 3, 5, 6, 7, 8 |
The two ways of making five don't need separate representation. This is a feasibility question, so true stays true. Counting subsets would require a different cell value and a different update operation.
A Complete Implementation
const canPartition = (nums: number[]): boolean => {
const total = nums.reduce((sum, value) => sum + value, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const reachable: boolean[] = Array(target + 1).fill(false);
reachable[0] = true;
for (const value of nums) {
for (let sum = target; sum >= value; sum -= 1) {
reachable[sum] = reachable[sum] || reachable[sum - value];
}
}
return reachable[target];
};We don't sort or mutate the input. Sorting isn't needed for the recurrence, and keeping the caller's array intact makes the function easier to reuse and test. Values above the target naturally perform no updates because the inner loop never starts.
The running time is O(n × target), with O(target) additional storage. This is often described as pseudo‑polynomial: its cost depends on the numeric target, rather than just the number of bits needed to write that target down.
For the problem's bounds of at most 200 values, each at most 100, the target is at most 10,000. A boolean table is a straightforward fit. For a small number of extremely large values, a different strategy such as dividing the items into halves and comparing subset sums can be more attractive. There's no need to make the interview solution carry that extra machinery for this input range.
Repeated Values are Not Repeated Use
For 3, 3, we should return true. The second occurrence is a different item, even though its value equals the first. Removing duplicates would change the problem and could destroy a valid answer.
That distinction separates two questions which are easy to blur. Can we use the current occurrence again during this pass? No. Can a later occurrence with the same value contribute? Yes. A descending pass per occurrence expresses exactly that behaviour.
Negative numbers would also change the design. A partial sum above the target could later fall, and the simple zero‑to‑target indexing would no longer cover all useful states. This code relies on the positive‑input promise rather than pretending to validate a general partitioning service.
Test the State Meaning, Not Just the Headline Example
I would keep a single positive item, an odd total, equal pairs, repeated values, a successful split requiring several items, and an even total with no solution. The forwards‑loop counterexample deserves its own named test because it protects the most easily broken line.
For stronger verification, enumerate every subset of short arrays and compare its sum with half the total. That reference deliberately avoids a reachability table. It is slower, but the independence is useful: copying the recurrence into a second function would mostly test whether I can repeat myself accurately.
Permuting the input should preserve the result. Multiplying every value by the same positive integer should also preserve feasibility, although it increases this implementation's table size. These properties supplement exact reference answers; a function returning false for everything would satisfy both.
My Coin Change walkthrough uses a table for a different question and permits repeated denominations. My Longest Increasing Subsequence article offers another example of deciding precisely what each stored value represents before compressing the state.
The Detail to Take Away
The reduction to half the total gives us the target. The descending loop gives us the correct supply of items. Both are part of the algorithm.
When I see an in‑place table update now, I ask which logical version of the source cell it reads. Here the answer must be the state before the current item. The backwards loop is how a small array keeps that promise.