Partition Equal Subset Sum

You are given an array nums of positive integers. Decide whether the elements can be divided into two groups with equal sums.

Every element must go into exactly one of the two groups, and the groups do not need to have the same number of elements. Return true if such a division exists and false otherwise.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Pattern Path · Dynamic Programming · problem 150 of 169

Start simple

Try all 2ⁿ ways to assign elements to the two groups: O(2ⁿ) time.

The key idea

If the two groups have equal sums, each must be exactly half of the total. So an odd total means the answer is immediately false, and otherwise the task is the classic subset-sum question: can some elements add up to target = total / 2? (The rest automatically form the other half.)

Keep a boolean array can where can[s] says whether some subset of the elements processed so far sums to s. Start with can[0] = true (the empty subset). When a new element x arrives, every previously reachable sum s also makes s + x reachable.

Loop over s from target down to x and set can[s] |= can[s - x]. Going downward ensures that can[s - x] still describes the state before x was added, so each element is used at most once. (Going upward would let one element be reused, which solves a different problem.)

The sums are bounded by 100 · 200 / 2 = 10,000, which makes this pseudo-polynomial DP fast.

Complexity

• Time: O(n · target)
• Space: O(target)

Python

class Solution:
    def canPartition(self, nums):
        total = sum(nums)
        if total % 2:
            return False              # an odd total can never be split evenly
        target = total // 2
        can = [False] * (target + 1)  # can[s]: some subset seen so far sums to s
        can[0] = True
        for x in nums:
            for s in range(target, x - 1, -1):   # downwards: use x at most once
                if can[s - x]:
                    can[s] = True
        return can[target]

JavaScript

var canPartition = function(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;         // an odd total can never be split evenly
  const target = total / 2;
  const can = new Array(target + 1).fill(false); // can[s]: some subset seen so far sums to s
  can[0] = true;
  for (const x of nums) {
    for (let s = target; s >= x; s--) {      // downwards: use x at most once
      if (can[s - x]) can[s] = true;
    }
  }
  return can[target];
};

What the interviewer is checking

This checks that you can reduce a partition question to 0/1 knapsack and explain why the one-dimensional DP must iterate sums in decreasing order.

Mistakes to avoid

• Forgetting the odd-total early exit (or dividing an odd total and rounding).
• Iterating sums upward in the 1-D DP, which reuses the same element several times.
• Assuming a greedy split (largest first into the lighter group) always works; it does not.

Follow-ups to expect

• Minimise the difference between the two group sums. (Largest reachable sum ≤ total/2.)
• Split into k groups with equal sums. (Backtracking with pruning or bitmask DP.)
• What if values are huge but n is small? (Meet in the middle.)

In real software

Balancing work between two machines, splitting a bill or inventory fairly, and load-balancing tasks across two servers are all instances of this subset-sum problem.

Practice next