Partition Equal Subset Sum

Medium15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonFacebookUber

Given an array of positive integers, determine whether it can be split into two subsets whose sums are equal. Every element must end up in exactly one of the two groups, and both groups together must use every element exactly once. An odd total can never be split evenly, so that case is ruled out immediately. Otherwise, finding an equal split is the same as finding any one subset that sums to exactly half the total — because whatever's left over automatically forms the other half, and since the two halves add up to the full total, matching one half automatically matches the other. That turns this into the familiar subset-sum search: try leaving each number out, try including it, and look for any combination that lands exactly on half the total.

Test Case 1:

Input:nums = [4, 2, 7, 1, 6]

Output:true

Explanation:Total is 20. Splitting into {4, 6} and {2, 7, 1} gives two groups that both sum to 10.

Test Case 2:

Input:nums = [9, 4, 6, 3]

Output:false

Explanation:Total is 22 (even), but no subset of {9, 4, 6, 3} sums to exactly 11.

Test Case 3:

Input:nums = [2, 2, 2]

Output:false

Explanation:Total is 6 (even), but every subset sums to an even number that never lands on 3.

Constraints

◆1 ≤ nums.length ≤ 20
◆1 ≤ nums[i] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Splitting the array into two equal-sum groups is only possible if the total is even in the first place — an odd total can never be split into two identical halves. When it is even, the question becomes: can some subset of the array sum to exactly half the total? Whatever that subset is, the rest of the array automatically forms the other half with the same sum. That reduces this problem to the same include/exclude search used for finding a subset that hits a target: at every number, try leaving it out and try taking it, and succeed the moment some combination reaches exactly half the total.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public boolean canPartition(int[] nums) {
        this.nums = nums;
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        return solve(0, total / 2);
    }

    private boolean solve(int i, int remaining) {
        if (remaining == 0) return true;
        if (i == nums.length || remaining < 0) return false;
        return solve(i + 1, remaining) || solve(i + 1, remaining - nums[i]);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

After confirming the total is even, the problem is exactly Subset Sum with a target of half the total: track, for every amount from 0 up to that half, whether some combination of the numbers seen so far can reach it exactly. Amount 0 always starts reachable, and each number extends every amount that was already reachable before it. Sweeping each number's inner update from the target down to that number's own value keeps every number's contribution limited to once per amount. Once every number has been swept through, the entry at half the total says whether an equal split exists.

TimeO(n × sum)

SpaceO(sum)