MediumArrayDynamic Programming

Partition Equal Subset Sum

1 approach, code in every language

You are given an array of positive integers. Determine whether the array can be divided into two subsets such that the sum of the elements in both subsets is exactly the same.

Every element must belong to exactly one of the two subsets, and neither subset may be empty in a valid equal split (though the standard framing simply asks whether such a balanced split exists).

Return true if such a partition is possible, and false otherwise.

Example 1

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

Output: true

The array can be split into {1,5,5} and {11}, both summing to 11, so an equal partition exists.

Example 2

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

Output: false

The total is 11, which is odd, so it can never be divided into two equal integer halves.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100
The total sum is at most 200 * 100 = 2 * 10^4

0/1 Subset Sum for Half the Total

If the total is odd the answer is immediately false; otherwise check whether some subset sums to exactly total/2 using a boolean DP over reachable sums.

Loading animation…

Intuition

If the two subsets must have equal sums, then each must equal half of the total, so the total has to be even to begin with. Once we know the target is total/2, the question becomes: can any subset of the numbers add up to that target? This is the classic 0/1 subset-sum problem. We track which sums are reachable using a boolean array, and each number may be used at most once. By iterating the sums from high to low we guarantee each number contributes to any given sum only a single time.

Algorithm walkthrough

1Compute the total sum; if it is odd, return false immediately because no equal integer split can exist.
2Set target = total / 2 and create a boolean array reachable of size target + 1 with reachable[0] = true.
3For each number, iterate s from target down to the number and mark reachable[s] true when reachable[s - num] is true.
4Iterating downward is essential: it prevents a single number from being counted more than once toward the same sum.
5After processing all numbers, return reachable[target], which tells whether a subset summing to half the total exists.

Implementation

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        reachable = [False] * (target + 1)
        reachable[0] = True
        for num in nums:
            for s in range(target, num - 1, -1):
                if reachable[s - num]:
                    reachable[s] = True
        return reachable[target]

Time

O(n * target) where target is half the total sum; each number sweeps the reachable-sum range once.

Space

O(target) for the single boolean array of reachable sums.

The odd-total early exit avoids allocating the DP table in roughly half the inputs.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Even Split of Crate Loads is our own problem on the technique behind Partition Equal Subset Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free