Partition Equal Subset Sum

medium2D Dynamic Programming62 stepsJava · Python · C++

Can the array be split into two parts with equal sums? Only if some subset sums to half the total. dp[s] says whether sum s is reachable; for each number, update sums from high to low so each number is used once.

▶ Watch the animated trace

Traced input: nums = [1, 5, 11, 5] → true. Original problem: neetcode.io/problems/partition-equal-subset-sum

Complexity

BestO(n·S)

AverageO(n·S)

WorstO(n·S)

SpaceO(S)

S = total / 2. The 2D table collapses to one row.

Key idea

An odd total can never be split evenly.
Target = total / 2; it's a subset-sum question.
Iterate sums downward so a number isn't reused within the same round.
Stop early if the target becomes reachable.

Common mistakes

Iterating sums upward turns it into unbounded knapsack (reuses numbers).
Forgetting the odd-total check.

Solution

Java

boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) {
        return false;
    }
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int i = 0; i < nums.length; i++) {
        for (int s = target; s >= nums[i]; s--) {
            dp[s] = dp[s] || dp[s - nums[i]];
        }
        if (dp[target]) {
            return true;
        }
    }
    return false;
}

Python

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

C++

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) {
        return false;
    }
    int target = total / 2;
    vector<bool> dp(target + 1);
    dp[0] = true;
    for (int x : nums) {
        for (int s = target; s >= x; s--) {
            dp[s] = dp[s] || dp[s - x];
        }
        if (dp[target]) {
            return true;
        }
    }
    return false;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Odd total Total 11 can't be halved.	`nums = [1, 2, 3, 5]`	`false`
Even total, still impossible Total 8 gives target 4, but no subset sums to 4.	`nums = [1, 2, 5]`	`false`
Two equal numbers One each side.	`nums = [3, 3]`	`true`
Single number Target 1 can't be made from a single 2.	`nums = [2]`	`false`