Partition Equal Subset Sum

Medium Dynamic Programming Knapsack Original on LeetCode

Partition Equal Subset Sum is a medium dynamic programming problem solved with the knapsack pattern. The best approach, optimal (1d subset-sum array), runs in O(n · target) time and O(target) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (pick or skip each number) up.

Problem

You are given an array nums of positive integers. Decide whether its elements can be split into two groups with equal sums. Every element must go into exactly one of the two groups.

Return true if such a split exists and false otherwise.

Examples

Example 1

Input
nums = [4, 9, 2, 7]
Output
true
Why
Total is 22. The groups [9, 2] and [4, 7] both sum to 11.

Example 2

Input
nums = [3, 3, 8]
Output
false
Why
Total is 14, so each group would need 7, but no subset of {3, 3, 8} adds up to 7.

Example 3

Input
nums = [5, 1, 2]
Output
false
Why
Total is 8, so each half is 4; 5 alone is too big and 1 + 2 = 3 is too small.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (pick or skip each number)O(2^n)O(n)
Better (2D reachability table)O(n · target)O(n · target)
Optimal (1D subset-sum array)O(n · target)O(target)

1Brute force (pick or skip each number)

TimeO(2^n)Every number doubles the number of subsets to try.
SpaceO(n)The recursion goes at most n levels deep.

Compute target = total / 2 (false if total is odd). Recursively try every subset: each number is either included in the running sum or skipped. Succeed as soon as some choice hits the target exactly.

  1. If the total is odd, return false; target = total / 2.
  2. search(i, sum): if sum == target return true; if i == n or sum > target return false.
  3. Return search(i + 1, sum + nums[i]) || search(i + 1, sum).
class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        return search(nums, 0, 0, total / 2);
    }

    private boolean search(int[] nums, int i, int sum, int target) {
        if (sum == target) return true;
        if (i == nums.length || sum > target) return false;
        return search(nums, i + 1, sum + nums[i], target) || search(nums, i + 1, sum, target);
    }
}

2Better (2D reachability table)

TimeO(n · target)Each of the (n + 1) · (target + 1) cells is filled in O(1).
SpaceO(n · target)The whole table is stored.

The recursion only depends on (i, sum), and sum never exceeds the target. Build a table can[i][s]: whether some subset of the first i numbers sums to s. Each row comes from the previous one by either skipping or taking nums[i-1].

  1. Return false for an odd total; target = total / 2.
  2. can[0][0] = true.
  3. For i from 1 to n and s from 0 to target: can[i][s] = can[i-1][s] || (s >= nums[i-1] && can[i-1][s - nums[i-1]]).
  4. Return can[n][target].
class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2, n = nums.length;
        boolean[][] can = new boolean[n + 1][target + 1];
        can[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = 0; s <= target; s++) {
                can[i][s] = can[i - 1][s] || (s >= x && can[i - 1][s - x]);
            }
        }
        return can[n][target];
    }
}

3Optimal (1D subset-sum array)

TimeO(n · target)Each number sweeps the sums from target down to x once.
SpaceO(target)Only one array of target + 1 booleans.

Each row of the table only reads the row above, so one boolean array over sums is enough. Walk the sums from high to low for each number: then can[s - x] still holds the value from before x was considered, so every number is used at most once. Stop early once the target becomes reachable.

  1. Return false for an odd total; target = total / 2.
  2. can = boolean array of size target + 1 with can[0] = true.
  3. For each x in nums: for s from target down to x, set can[s] = can[s] || can[s - x].
  4. If can[target] is true, return true. After the loop, return can[target].
class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] can = new boolean[target + 1];
        can[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (can[s - x]) can[s] = true;
            }
            if (can[target]) return true;
        }
        return can[target];
    }
}

Edge cases to test

  • A single element can never be split into two non-empty equal groups
  • An odd total is immediately false
  • One element larger than half the total makes it impossible
  • Two equal elements, like [6, 6], are true

Hints

Hint 1

If the total is odd, stop. Otherwise the question becomes: is there a subset that sums to exactly total / 2? The rest automatically sums to the other half.

Hint 2

For each number you either put it in the subset or not. Let can[i][s] say whether some of the first i numbers sum to s.

Hint 3

Keep one boolean array over sums. For each number x, go through sums from high to low and set can[s] |= can[s - x], so x is used at most once.

FAQ

What is the best time complexity for Partition Equal Subset Sum?

Optimal (1D subset-sum array) runs in O(n · target) time and O(target) extra space. Each number sweeps the sums from target down to x once.

Which pattern does Partition Equal Subset Sum use?

It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.

Is there a brute force solution for Partition Equal Subset Sum?

Yes. Brute force (pick or skip each number) takes O(2^n) time and O(n) space. Compute target = total / 2 (false if total is odd).

Which edge cases should I test for Partition Equal Subset Sum?

A single element can never be split into two non-empty equal groups; An odd total is immediately false; One element larger than half the total makes it impossible; Two equal elements, like [6, 6], are true.