242. Partition Equal Subset Sum

Splitting nums into two subsets of equal sum is the same as picking a subset that sums to total / 2. (The complement automatically sums to the other half.) That's the classic 0/1 knapsack "can we hit target sum?" question. We track the set of reachable subset-sums as we add numbers one at a time.

Reframing

If total = sum(nums) is odd, no equal split is possible — return False immediately. Otherwise we want a subset summing to target = total // 2.

possible starts as {0} (the empty subset has sum 0). For each x in nums, every reachable sum s can be extended by including x to give s + x. So possible |= {s + x for s in possible if s + x <= target}.

We can short-circuit as soon as target enters possible.

Steps

1. total = sum(nums). If total is odd, return False.
2. target = total // 2. Initialise possible = {0}.
3. For each x in nums:
   • possible |= {s + x for s in possible if s + x <= target}.
   • If target in possible, return True.
4. After processing all numbers, return False.

Walk-through

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

So [1, 5, 5] and [11] both sum to 11.

Why we cap at target

Any subset-sum exceeding target is useless — we'd need its complement to be negative. Filtering with s + x <= target keeps the set small (at most target + 1 values).

Edge cases

• Odd total: impossible, return False.
• All zeros: target = 0, 0 is already in possible — actually we want a non-empty split? The problem definition usually allows True here.
• Single element: unless it equals zero or there's another zero, it can't split.

Complexity

• Time: O(n · target) = O(n · S/2) — for each number, the set update touches up to target values.
• Space: O(target) for the set.

(Python's set is a clean alternative to a bitset; using an integer-as-bitset gives the same complexity with a smaller constant.)

import java.util.*;

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        Set<Integer> possible = new HashSet<>();
        possible.add(0);
        for (int x : nums) {
            Set<Integer> next = new HashSet<>(possible);
            for (int s : possible) {
                if (s + x <= target) next.add(s + x);
            }
            possible = next;
            if (possible.contains(target)) return true;
        }
        return false;
    }
}