Partition Equal Subset Sum
Maintained by Vikas D, software engineer
You receive an array of positive integers. The goal is to tell whether the numbers can be divided into two groups so that both groups add up to the same total. Every number must land in exactly one of the two groups.
Because both halves must be equal, each one has to add up to exactly half of the whole array's sum. That immediately tells you something useful: if the total sum is odd, no split is possible, since half of an odd number is not a whole value that integer subsets can reach.
When the total is even, the question reduces to a single yes-or-no decision: can you pick a subset of the numbers that adds up to exactly half the total? If such a subset exists, the leftover numbers form the matching half automatically, so you only ever need to hunt for one of the two groups.
Return true if such an even split exists and false if it does not.
Examples
The total is 22, so each half must reach 11. The subset [1, 5, 5] sums to 11 and the remaining [11] also sums to 11.
The total is 11, an odd number, so no two subsets can ever tie. The answer is false without checking any combination.
The total is 18, so each half needs 9. Picking [4, 5] reaches 9 and the three 3s on the other side also reach 9.
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
- All values are positive, so the target half is a fixed non-negative integer.
- The total sum is at most 200 * 100 = 20000, which bounds the half-sum used by the table.
Visible test cases
- canPartition([1,5,11,5]) == true
- canPartition([1,2,3,5]) == false
- canPartition([1,1]) == true
- canPartition([3,3,3,4,5]) == true
- canPartition([1,2,5]) == false
Hints
Hint 1
First check the total sum. If it is odd, you can stop right away and return false.
Hint 2
When the total is even, you no longer need both groups. Ask a simpler question: is there a subset that adds up to half the total?
Hint 3
Track every subset sum you can build as you walk through the numbers. A boolean array indexed by sum, updated one number at a time, answers the subset question without listing actual subsets.
Approaches
Brute force subset search
Time O(2^n) because each of the n numbers is either taken or left out. · Space O(n) for the recursion stack depth.Try every possible subset and see if any one reaches half of the total sum.
- Compute the total sum and return false if it is odd.
- Set target to half the total.
- Recurse over the numbers, at each step either including the current number in the running sum or skipping it.
- Return true the moment the running sum equals target; return false if you exhaust all numbers without hitting it.
Optimal subset-sum dynamic programming
Time O(n * target) where target is at most half the sum, so roughly O(n * sum). · Space O(target) for the single boolean row.Treat it as a 0/1 knapsack: track which sums up to target are reachable using a one-dimensional boolean table, updated right to left so each number is used at most once.
- Compute the total sum and return false immediately if it is odd.
- Set target to total / 2 and create a boolean array reachable of length target + 1, with reachable[0] = true.
- For each number n, sweep s from target down to n and mark reachable[s] true whenever reachable[s - n] is already true.
- Iterating from high to low keeps each number from being counted twice within the same pass.
- After processing every number, return reachable[target].
Common mistakes
- Forgetting the odd-total shortcut and running the table on an odd sum, where target / 2 is not an integer and the answer is always false anyway.
- Sweeping the inner loop from low to high instead of high to low, which lets one number be reused multiple times and turns the problem into unbounded knapsack.
- Sizing the boolean array to the full sum instead of just target + 1, wasting roughly double the memory.
- Trying to enumerate or store the actual subsets, which is unnecessary since only the reachability of the target matters.
Follow-up variations
- Return the two subsets themselves, not just whether the split exists.
- Allow the array to contain zeros or negative numbers and re-derive the target logic.
- Generalize to splitting into k equal-sum groups instead of two.
- Minimize the absolute difference between the two group sums when an exact tie is impossible.