Partition Equal Subset Sum

Medium0/1 Knapsack (DP)NeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of positive integers. Decide whether you can split it into two groups with equal sums, where every element goes into exactly one group and the groups don't need to be contiguous. Return true if such a split exists and false otherwise.

Examples

nums = [1,5,11,5] returns true

The total is 22, so each group needs 11. [1,5,5] and [11] both sum to 11.

nums = [1,2,3,5] returns false

The total is 11, which is odd, so it can't be split into two equal whole-number halves.

nums = [1,2,5] returns false

The total, 8, is even, so each group would need 4. No combination of 1, 2 and 5 adds up to 4, so the split is impossible.

Constraints

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

Hints

Hint 1

If the total sum is odd you can stop early: otherwise, what's the smaller question that's equivalent?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

If the total is odd, return false. Otherwise ask whether some subset sums to target = total / 2, since the rest then sums to target too. Keep a boolean array dp where dp[s] is true if some subset of the numbers seen so far sums to s, starting with dp[0] = true. For each number n, sweep s from target down to n and set dp[s] = dp[s] or dp[s - n]; sweeping downward uses each number at most once. O(n * target) time, O(target) space.

Time

O(n * target)

Space

O(target)

Pitfall

Sweeping s upward lets one number be reused within the same pass. With nums = [1,2,5], processing 1 upward marks every sum from 1 to 4 as reachable, and you wrongly return true.

Solutions

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int n : nums) {
            for (int s = target; s >= n; s--) {
                dp[s] = dp[s] || dp[s - n];
            }
        }
        return dp[target];
    }
}

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