Partition Equal Subset Sum
Problem
nums, decide whether you can split
it into two groups (every element used exactly once) whose sums are equal.[1,5,11,5]Outputtrue ({1,5,5} | {11})[1,2,3,5]Outputfalse1 ≤ n ≤ 200 · 1 ≤ nums[i] ≤ 100
Try it yourself
class Solution {
public boolean canPartition(int[] nums) {
}
}
false; otherwise ask: does some
subset sum to total/2? (the rest automatically makes the other half). That is
a 0/1 knapsack over sums 0..total/2.Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.
Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.
Open the Knapsack DP guide →Approaches
Brute ForceInclude / Exclude Recursion
O(2n)Space O(n)For each index, either put nums[i] into the subset (reduce the
remaining target) or leave it out. Succeed when the remaining target hits 0. Every
element doubles the number of paths.
public boolean canPartition(int[] nums) { int total = 0; for (int x : nums) total += x; if (total % 2 != 0) return false; return can(nums, 0, total / 2); } private boolean can(int[] nums, int i, int rem) { if (rem == 0) return true; if (i == nums.length || rem < 0) return false; return can(nums, i + 1, rem - nums[i]) || can(nums, i + 1, rem); }
Simple, but 2200 paths in the worst case.
BetterMemoization on (index, remaining)
O(n·S)Space O(n·S)The recursion state is only (i, rem) with
rem ≤ S = total/2, so there are at most n·S
distinct calls. Cache them in a Boolean[n][S+1] table
(null = unknown).
public boolean canPartition(int[] nums) { int total = 0; for (int x : nums) total += x; if (total % 2 != 0) return false; return can(nums, 0, total / 2, new Boolean[nums.length][total / 2 + 1]); } private boolean can(int[] nums, int i, int rem, Boolean[][] memo) { if (rem == 0) return true; if (i == nums.length || rem < 0) return false; if (memo[i][rem] != null) return memo[i][rem]; return memo[i][rem] = can(nums, i + 1, rem - nums[i], memo) || can(nums, i + 1, rem, memo); }
Polynomial (pseudo-polynomial), but a 2-D table and deep recursion.
Optimal1-D Bottom-Up Knapsack
O(n·S)Space O(S)dp[s] = “some subset of the numbers seen so far sums to
s”. For each number, dp[s] |= dp[s - num]. Loop
s downwards so a number is used at most once in its own round.
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[] dp = new boolean[target + 1]; dp[0] = true; // empty subset for (int num : nums) { for (int s = target; s >= num; s--) { dp[s] = dp[s] || dp[s - num]; } if (dp[target]) return true; } return dp[target]; }
Dry run[2,3,5] → total 10, target 5; cells = dp[0..5]
- initTFFFFFtonly sum 0 reachable
- num=2TFTFFFtdp[2] |= dp[0]
- num=3TFTTFTtdp[5] |= dp[2] ✔
Same time, one boolean row of size S+1 — standard answer.
BitSet/long shift (bits |= bits << num)
processes 64 sums per operation.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Include / Exclude Recursion | O(2n) | O(n) |
| Better | Memoization on (index, remaining) | O(n·S) | O(n·S) |
| Optimal | 1-D Bottom-Up Knapsack | O(n·S) | O(S) |
- Skipping the odd-total check —
total/2silently rounds down. - Iterating
supwards in 1-D — reuses a number (unbounded knapsack). - Memoizing with primitive
boolean— can't tell “false” from “unknown”.
- Reduce to subset-sum first; say it out loud before coding.
- Mention it is pseudo-polynomial: O(n·S) depends on the values, not just n.
- Show the 2-D → 1-D compression and why the loop must go backwards.