LeetCode 416: Partition Equal Subset Sum

Problem Restatement

We are given an integer array nums.

Return True if we can split the array into two subsets such that both subsets have the same sum.

Otherwise, return False.

Each number can be used at most once, because every element belongs to exactly one of the two subsets.

The source problem gives examples such as nums = [1,5,11,5], which returns true, and nums = [1,2,3,5], which returns false. The constraints are 1 <= nums.length <= 200 and 1 <= nums[i] <= 100.

Input and Output

Example function shape:

def canPartition(nums: list[int]) -> bool:
    ...

Examples

Example 1:

nums = [1, 5, 11, 5]

The answer is:

True

One valid partition is:

[1, 5, 5] and [11]

Both subsets have sum:

11

Example 2:

nums = [1, 2, 3, 5]

The answer is:

False

The total sum is:

1 + 2 + 3 + 5 = 11

Since 11 is odd, it cannot be split into two equal integer sums.

First Thought: Try Every Subset

A direct approach is to try every possible subset.

For each subset, compute its sum.

If any subset has sum equal to half of the total array sum, then the remaining elements automatically form the other half.

But there are:

2^n

possible subsets.

With up to 200 numbers, this is too slow.

Key Insight

If the total sum is odd, equal partition is impossible.

If the total sum is even, each subset must have sum:

target = total_sum // 2

So the problem becomes:

Can we choose some numbers from nums whose sum is exactly target?

This is the classic 0/1 knapsack subset-sum problem.

Each number can be chosen once or skipped once.

Dynamic Programming Idea

Let:

dp[s]

mean:

Can we form sum s using the numbers processed so far?

Initially:

dp[0] = True

because sum 0 can always be formed by choosing nothing.

For each number num, update possible sums.

If sum s - num was possible before using num, then sum s becomes possible after using num.

So:

dp[s] = dp[s] or dp[s - num]

We must scan s backward from target down to num.

This prevents using the same number more than once.

Algorithm

1. Compute the total sum.
2. If the total sum is odd, return False.
3. Set target = total_sum // 2.
4. Create a boolean array dp of size target + 1.
5. Set dp[0] = True.
6. For each num in nums:
   • For s from target down to num:
     • If dp[s - num] is true, set dp[s] = True.
7. Return dp[target].

Correctness

The dynamic programming invariant is:

After processing the first i numbers, dp[s] is true exactly when some subset of those first i numbers has sum s.

Before processing any number, only sum 0 is possible, so dp[0] = True is correct.

When processing a number num, each target sum s has two possibilities.

We can skip num, in which case dp[s] remains as it was.

Or we can use num, in which case we need a previous subset with sum s - num.

So the update:

dp[s] = dp[s] or dp[s - num]

captures exactly these two choices.

The backward loop ensures num is used at most once. If we looped forward, dp[s - num] might already include the current num, causing repeated use.

After all numbers are processed, dp[target] is true exactly when some subset sums to half of the total sum.

If such a subset exists, the remaining numbers also sum to the same value. Therefore, the array can be partitioned into two equal-sum subsets.

If no such subset exists, no equal partition is possible.

Complexity

Here:

Given the constraints, sum(nums) is at most 200 * 100 = 20000, so target is at most 10000.

Implementation

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)

        if total % 2 == 1:
            return False

        target = total // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for s in range(target, num - 1, -1):
                dp[s] = dp[s] or dp[s - num]

            if dp[target]:
                return True

        return dp[target]

Code Explanation

We compute the total sum:

total = sum(nums)

If the total is odd:

if total % 2 == 1:
    return False

then equal partition is impossible.

The target subset sum is:

target = total // 2

The array:

dp = [False] * (target + 1)

tracks which sums can be formed.

We set:

dp[0] = True

because choosing no elements gives sum 0.

For each number:

for num in nums:

we update possible sums in reverse:

for s in range(target, num - 1, -1):

The update:

dp[s] = dp[s] or dp[s - num]

means sum s is possible if it was already possible, or if we can make s - num before adding num.

We can return early when target becomes possible:

if dp[target]:
    return True

Finally:

return dp[target]

returns whether half the total sum can be formed.

Testing

def test_can_partition():
    s = Solution()

    assert s.canPartition([1, 5, 11, 5]) is True
    assert s.canPartition([1, 2, 3, 5]) is False
    assert s.canPartition([1, 1]) is True
    assert s.canPartition([2, 2, 3, 5]) is False
    assert s.canPartition([100, 100]) is True
    assert s.canPartition([1, 2, 5]) is False
    assert s.canPartition([3, 3, 3, 4, 5]) is True

    print("all tests passed")

Test Notes