Partition Equal Subset Sum
Problem Statement
Given an integer array nums, return true if you can partition the array into two subsets whose sums are equal. Each number must belong to exactly one of the two subsets.
Input
An integer array nums containing positive values.
Output
A boolean: true if the array can be split into two equal-sum subsets, otherwise false.
Constraints
- •
1 <= nums.length <= 200 - •
1 <= nums[i] <= 100
Examples
Example 1
nums = [1,5,11,5]
trueExample 2
nums = [1,2,3,5]
falseExample 3
nums = [2,2,3,5]
falseLearning Objectives
- Reduce equal partition to the classic subset-sum target **total / 2**.
- Use a 1D boolean DP array to represent reachable capacities after each item prefix.
- Explain why 0/1 knapsack scans capacity descending so an item is not reused in the same iteration.
- Recognise the parity check as an early impossibility test before building DP state.
Intuition
If the array can be split into two subsets with equal sum, the total sum must be even. Once that is true, the entire problem becomes one question: can we pick some numbers whose sum is exactly total / 2? The other numbers automatically form the second half.
This is a choose-or-skip problem. For each number, either it participates in the target subset or it does not. That is the 0/1 knapsack pattern: every item is available once, and capacity is the target sum.
The subtle part is compressing the item dimension into one array. When processing a number, scanning capacities from high to low preserves the previous row for smaller capacities. If you scan upward, dp[num] can become true and then immediately help set dp[2 * num] during the same number, which accidentally changes 0/1 knapsack into unbounded knapsack.
Common mistakes
- ×Starting DP without checking whether the total sum is odd.
- ×Scanning capacity ascending and accidentally allowing the same number to be used multiple times.
- ×Treating the problem as two independent subset searches instead of one target subset search.
- ×Using a 2D table when the previous item row can be safely compressed into one descending scan.
State Definition
Let dp[c] mean whether some subset of the numbers processed so far can make sum exactly c. The answer is dp[target], where target = total / 2.
State Transition
For a new number num and capacity c, there are two choices. Skip it, so dp[c] stays true if it was already true. Take it, which is possible when c >= num and the previous row could make c - num.
The compressed recurrence is dp[c] = dp[c] OR dp[c - num] for c from target down to num.
Base case: dp[0] = true, because the empty subset makes sum 0. The descending capacity loop is essential: it keeps dp[c - num] from being updated by the current num, so each number is used at most once.
Solutions
Solution: 1D 0/1 subset-sum DP
Compute the half-sum target, then maintain which capacities are reachable while processing each number once. The outer loop chooses the item, and the inner loop scans capacity descending to preserve 0/1 usage.
Step-by-step
- Sum the array and return false immediately if the total is odd.
- Set target = total / 2 and initialise dp[0] = true.
- For every num, scan capacities from target down to num.
- Mark dp[c] reachable if it was already reachable or if c - num was reachable before this number.
- Return dp[target] after all numbers are processed.
O(n · target)
O(target)
There are n numbers and each updates at most target capacities once.
Java implementation
Dry Run
Sample input
nums = [1, 5, 11, 5]. The total is 22, so the subset target is 11.
| item | capacity scan | reachable sums after item | reason |
|---|---|---|---|
| 1 | 11 down to 1 | {0, 1} | Only sum 1 becomes newly reachable from 0. |
| 5 | 11 down to 5 | {0, 1, 5, 6} | Taking 5 alone makes 5; taking it with 1 makes 6. |
| 11 | 11 down to 11 | {0, 1, 5, 6, 11} | The target 11 becomes reachable, so an equal partition exists. |
| 5 | 11 down to 5 | {0, 1, 5, 6, 10, 11} | The answer stays true; descending order still uses this final 5 only once. |
The first time 11 appears in the reachable set, we have found one half of the partition. The remaining numbers must sum to the other half because the total is exactly 22.
Complexity Analysis
The optimal interview solution is the compressed 0/1 subset-sum table. The key correctness point is descending capacity iteration, not just the recurrence.
1D 0/1 subset-sum DP
O(n · target)
O(target)
There are n numbers and each updates at most target capacities once.
Interview Tips
Start by saying that equal partition is subset sum with target total / 2. Then make the loop direction explicit: because every number can be chosen at most once, the capacity loop must go downward. Interviewers often use this problem to check whether you understand why 1D knapsack compression works.
Likely follow-ups
- Return one actual subset that forms the equal partition.
- Count how many subsets sum to **total / 2** instead of returning a boolean.
- What changes if each number may be used unlimited times?
- How would you minimise the absolute difference between the two subset sums?
Similar Problems
Key Takeaways
- Equal partition reduces to finding one subset with sum **total / 2**.
- 0/1 knapsack compression scans capacity descending to avoid reusing the current item.
- The empty subset base case **dp[0] = true** starts all reachable-sum DP tables.
- An odd total makes the problem impossible before DP begins.