4.23.12 — Partition Equal Subset Sum

LeetCode 416 · Medium

The problem

Return true if the array can be split into two subsets with equal sums.

[1,5,11,5]   →  true    ([1,5,5] and [11])
[1,2,3,5]    →  false

Up to 200 numbers, each at most 100.

The pattern

Two reductions, and the first one halves the problem.

Reduction 1. If the two halves have equal sums, each equals total / 2. So the question becomes: is there a subset summing to exactly total / 2? You never need to think about the second subset — whatever is left over is automatically the other half.

And if the total is odd, the answer is immediately false. That check costs one line and rejects a large fraction of inputs.

Reduction 2. "Is there a subset summing to exactly T" is the 0/1 knapsack decision problem — each item is either taken or not, and you want to hit a target exactly.

Enumerating all 2^n subsets is far too slow at n = 200. But the sums are bounded: at most 200 × 100 / 2 = 10,000. Bounded values mean a table indexed by value, and that is what makes it tractable.

Let dp[t] be true when some subset sums to exactly t.

The solution

Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False                     # cannot split an odd total

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True                         # the empty subset sums to 0

        for n in nums:
            for t in range(target, n - 1, -1):        # DOWNWARDS — see below
                dp[t] = dp[t] or dp[t - n]
            if dp[target]:
                return True                  # early exit

        return dp[target]

TypeScript

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;

  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const n of nums) {
    for (let t = target; t >= n; t--) {
      dp[t] = dp[t] || dp[t - n];
    }
    if (dp[target]) return true;
  }

  return dp[target];
}

The loop direction, which is the whole point

The inner loop counts downwards, and that is what stops an item being used twice.

Here is why. When you process item n and read dp[t - n], you want that value to describe subsets formed from the previous items only — not subsets that already include n.

• Going downwards, dp[t - n] is at a lower index that has not been updated yet in this round, so it still holds the value from before this item. The item is used at most once. 0/1 knapsack.
• Going upwards, dp[t - n] may already have been updated in this round to include n, so n gets used again. Unbounded knapsack.

One character of loop direction, two completely different problems. This is the trap named in 4.22, and it is the reason to understand rolling arrays rather than copy them.

Compare directly:

# each item ONCE  (this problem)
for n in nums:
    for t in range(target, n - 1, -1): ...

# items REUSABLE  (Coin Change, 4.23.8)
for c in coins:
    for t in range(c, target + 1): ...

When you meet a DP whose loop runs backwards and you cannot see why, this is almost always the reason.

The other details

dp[0] = True — the empty subset sums to zero, and every other reachable sum is built from it.

range(target, n - 1, -1) stops at n, because below n the item cannot be used and dp[t - n] would index negatively.

The early exit is a real saving on inputs that reach the target quickly.

Trace

[1, 5, 11, 5], total 22, target 11.

item	sums now reachable
start	{0}
1	{0, 1}
5	{0, 1, 5, 6}
11	{0, 1, 5, 6, 11, ...} → dp[11] true → return true

The subset is [11], leaving [1, 5, 5] which also sums to 11 ✓.

The bitset trick

There is a one-line version that is dramatically faster in practice:

bits = 1                                     # bit t set means "sum t is reachable"
for n in nums:
    bits |= bits << n
return (bits >> (total // 2)) & 1 == 1

bits << n shifts every reachable sum up by n — that is, adds n to all of them at once — and |= merges the new sums with the old.

Python's unbounded integers make this legal, and the CPU processes 64 sums per machine word, so it is roughly 64 times faster than the loop with the same asymptotic bound. Know it, and write the explicit loop in an interview — the point of the question is the knapsack, and the bitset hides it.

Complexity

O(n \times \text{target}) time, which is O(n \times \text{sum}). With n = 200 and sums up to 10,000, that is 2 million operations.

O(\text{target}) space.

This is pseudo-polynomial, the same caveat as 4.23.8 Coin Change: polynomial in the value of the sum, not in the number of bits used to write it. The subset-sum problem is NP-complete in general, and this table only works because the values are small. Saying that out loud is a strong signal — it shows you know the difference between "I found a polynomial algorithm" and "the constraints let me get away with a table".

Where this goes next

• Target Sum — assign + or − to each number to reach a target. It reduces to subset sum with the target (total + S) / 2, and deriving that reduction is the whole problem. 4.24.5.
• Last Stone Weight II — minimise the difference between two groups, which is subset sum closest to total / 2.
• Partition to K Equal Sum Subsets — much harder; needs backtracking with a bitmask of used items.
• 0/1 knapsack with values — the same loop with max(dp[t], dp[t-w] + v) instead of or.

The four knapsack shapes, worth learning as a set: reachability (or), counting (+), maximising value (max), and unbounded versions of each — which differ only in the loop direction.

What the interviewer will push on

"How do you reduce this to one subset?" Equal halves each sum to total / 2, so finding one is enough.

"What if the total is odd?" Immediately false.

"Why does the inner loop go downwards?" So each item is used at most once. This is the question, and being able to explain both directions is what separates understanding from copying.

"What is the complexity, and is that polynomial?" O(n \times \text{sum}), pseudo-polynomial, and subset sum is NP-complete in general.

"Could you return the actual subset?" Keep the 2-D table instead of rolling it, then walk backwards asking at each item whether the sum was reachable without it.

One thing to volunteer: name it as 0/1 knapsack before writing anything, and say that the loop direction is what enforces the "0/1". That single sentence covers the reduction and the trap together.

Next: 4.24 adds the second dimension — grids, two sequences compared, and the interval problems whose O(n^3) you can read straight off the state count.