Partition Equal Subset Sum (LeetCode 416)

The problem

Given an array nums of positive integers, return True if it can be split into two subsets with equal sums, otherwise False. Every element goes into exactly one of the two subsets.

Input:  nums = [1, 5, 11, 5]
Output: True

Input:  nums = [1, 2, 3, 5]
Output: False

[1, 5, 5] and [11] both sum to 11. For [1, 2, 3, 5] the total is 11, which is odd, so no equal split exists.

How to think about it

Start with brute force. Try every way to assign each number to side A or side B: O(2ⁿ). With up to 200 numbers that is hopeless.

First reduction: you only need one side. If the two halves are equal, each sums to total / 2. So the question becomes “is there a subset that sums to target = total / 2?” If total is odd, the answer is immediately False. The rest of the numbers automatically form the other half.

The key insight: track which sums are reachable. Process the numbers one at a time and keep the set of sums you can make from the numbers seen so far. Each new number x either stays out (every old sum is still reachable) or joins (every old sum t gives a new sum t + x). That is the 0/1 knapsack choice, and the set never holds more than target + 1 values because sums above target are useless.

Which pattern is this? 0/1 knapsack, as a 1-D DP over sums. The tell is “split into two equal groups” or “pick a subset hitting a target”, where each item is used at most once.

Approach

1. Compute total. If it’s odd, return False.
2. Set target = total // 2 and dp = {0} (the empty subset).
3. For each x: add x + t to dp for every t already in dp, keeping only sums <= target.
4. Return whether target is in dp.

Solution

def can_partition(nums):
    total = sum(nums)
    if total % 2: return False                    # odd total can't split evenly
    target = total // 2; dp = {0}                 # dp = sums reachable so far
    for x in nums:
        dp |= {x + t for t in dp if x + t <= target}   # x joins each old sum (or stays out)
    return target in dp
# can_partition([1,5,11,5]) -> True ;  can_partition([1,2,3,5]) -> False

The set comprehension is built from the old dp before |= merges it, so each number is used at most once.

Dry run

On [1, 5, 11, 5]: total = 22, target = 11.

11 is reachable, so the answer is True.

Complexity

• Time: O(n · target). Each number touches at most target + 1 sums.
• Space: O(target). The set of reachable sums. A boolean array dp[0..target] iterated from high to low works the same way.

Edge cases and pitfalls

• Odd total returns False before any DP.
• Single element ([2]) returns False: one side would be empty with sum 0.
• With a boolean array, iterate sums downwards. Going upwards lets the same number be added twice (that’s unbounded knapsack, as in Coin Change II).
• Early exit: you can return True the moment target enters dp.

Related problems

• Partition to K Equal Sum Subsets (LeetCode 698): the generalisation to k groups, which needs backtracking or bitmask DP.
• Coin Change II (LeetCode 518): the unbounded version, where each item can be reused.
• Subsets (LeetCode 78): the brute force this DP replaces, listing every subset.