The problem. Given an array of positive integers nums, return true if it can be split into two subsets with equal sums.
![nums is 1, 5, 11, 5. The total is 22, so each half must sum to 11. A row of booleans can[0..11] records which sums some subset can make. It starts with only can[0]. Adding 1 makes 1 reachable; adding 5 makes 5 and 6; adding 11 makes 11; the last 5 makes 10. can[11] is true: 11 on one side, 1 + 5 + 5 on the other.](/drawings/16e541c7-cb99-4030-8d48-0c3eef41a994.svg)
nums = [1, 5, 11, 5] -> true ([11] and [1, 5, 5])
nums = [1, 2, 3, 5] -> false (the total, 11, is odd)
nums = [1, 2, 5] -> false (total 8, but no subset makes 4)If the two halves are equal, each is total / 2. So an odd total is an instant false, and otherwise the question becomes: can some subset make exactly `target = total / 2`? The other half is then whatever is left. That's the 0/1 knapsack shape: each number is either in the bag or not, and the state is (which numbers you've looked at, which sum you need).
function canPartition(nums) { const total = nums.reduce((a, b) => a + b, 0); if (total % 2 === 1) return false; // an odd total can't split evenly const reach = (i, left) => { // can nums[i..] make exactly left? if (left === 0) return true; if (i === nums.length || left < 0) return false; return reach(i + 1, left - nums[i]) || reach(i + 1, left); // take nums[i], or skip it }; return reach(0, total / 2);}Time O(2ⁿ), space O(n). Every number branches twice. But the arguments are only (i, left): at most n × (target + 1) different calls, so most of those 2ⁿ calls are repeats.
function canPartition(nums) { const total = nums.reduce((a, b) => a + b, 0); if (total % 2 === 1) return false; const memo = new Map(); // "i,left" -> answer const reach = (i, left) => { if (left === 0) return true; if (i === nums.length || left < 0) return false; const key = i + "," + left; if (!memo.has(key)) memo.set(key, reach(i + 1, left - nums[i]) || reach(i + 1, left)); return memo.get(key); }; return reach(0, total / 2);}Time O(n · target), space O(n · target). Each (i, left) pair is solved once. This is pseudo-polynomial: fast when the numbers are small (LeetCode caps the sum at 20,000), slow if they could be in the billions.
Each number lights up new sums, scanning from high to low.
function canPartition(nums) { const total = nums.reduce((a, b) => a + b, 0); if (total % 2 === 1) return false; const target = total / 2; const can = new Array(target + 1).fill(false); // can[s]: some subset so far sums to s can[0] = true; // the empty subset for (const x of nums) { for (let s = target; s >= x; s--) { // backwards: each number is used once if (can[s - x]) can[s] = true; } } return can[target];}Time O(n · target), space O(target). The full table would have a row per number, but each row only reads the row above, so one row is updated in place.
Why backwards? When s goes from high to low, can[s - x] is still the value from before x was added, so x is counted at most once. Scan upwards and can[s - x] may already include x — then x is reused as often as you like. That's the other knapsack, the unbounded one, and it's exactly what Coin Change needs.
false without any work.false: one side would be empty.false: it can't fit on either side.[7, 7] is true.total / 2.bits |= bits << x updates the whole row in one shift.