Partition Equal Subset Sum
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 <= 2001 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(2^n)Every number doubles the number of subsets to try.O(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.
- If the total is odd, return false; target = total / 2.
- search(i, sum): if sum == target return true; if i == n or sum > target return false.
- 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);
}
}class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
n = len(nums)
def search(i: int, s: int) -> bool:
if s == target:
return True
if i == n or s > target:
return False
return search(i + 1, s + nums[i]) or search(i + 1, s)
return search(0, 0)class Solution {
bool search(const vector<int>& nums, int i, int sum, int target) {
if (sum == target) return true;
if (i == (int)nums.size() || sum > target) return false;
return search(nums, i + 1, sum + nums[i], target) || search(nums, i + 1, sum, target);
}
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2 != 0) return false;
return search(nums, 0, 0, total / 2);
}
};function canPartition(nums) {
let total = 0;
for (const x of nums) total += x;
if (total % 2 !== 0) return false;
const target = total / 2;
const search = (i, sum) => {
if (sum === target) return true;
if (i === nums.length || sum > target) return false;
return search(i + 1, sum + nums[i]) || search(i + 1, sum);
};
return search(0, 0);
}2Better (2D reachability table)
O(n · target)Each of the (n + 1) · (target + 1) cells is filled in O(1).O(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].
- Return false for an odd total; target = total / 2.
- can[0][0] = true.
- 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]]).
- 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];
}
}class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target, n = total // 2, len(nums)
can = [[False] * (target + 1) for _ in range(n + 1)]
can[0][0] = True
for i in range(1, n + 1):
x = nums[i - 1]
for s in range(target + 1):
can[i][s] = can[i - 1][s] or (s >= x and can[i - 1][s - x])
return can[n][target]class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2 != 0) return false;
int target = total / 2, n = nums.size();
vector<vector<bool>> can(n + 1, vector<bool>(target + 1, false));
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];
}
};function canPartition(nums) {
let total = 0;
for (const x of nums) total += x;
if (total % 2 !== 0) return false;
const target = total / 2, n = nums.length;
const can = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(false));
can[0][0] = true;
for (let i = 1; i <= n; i++) {
const x = nums[i - 1];
for (let 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)
O(n · target)Each number sweeps the sums from target down to x once.O(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.
- Return false for an odd total; target = total / 2.
- can = boolean array of size target + 1 with can[0] = true.
- For each x in nums: for s from target down to x, set can[s] = can[s] || can[s - x].
- 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];
}
}class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
can = [False] * (target + 1)
can[0] = True
for x in nums:
for s in range(target, x - 1, -1):
if can[s - x]:
can[s] = True
if can[target]:
return True
return can[target]class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2 != 0) return false;
int target = total / 2;
vector<bool> can(target + 1, false);
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];
}
};function canPartition(nums) {
let total = 0;
for (const x of nums) total += x;
if (total % 2 !== 0) return false;
const target = total / 2;
const can = new Array(target + 1).fill(false);
can[0] = true;
for (const x of nums) {
for (let 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.