medium
Partition Equal Subset Sum
Given an array of positive integers, decide whether it can be split into two groups with equal sums.
Constraints
- 1 ≤ n ≤ 200
- 1 ≤ nums[i] ≤ 100
Examples
in: nums = [1,5,11,5]
out: true
{1,5,5} and {11}.
in: nums = [1,2,3,5]
out: false
Recognition clues
- Equivalent to "is there a subset with sum total/2"
- 0/1 knapsack with a boolean reachability table
- Small total (≤ 20000) makes the table feasible
Pattern
Dynamic ProgrammingCounting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Solution
If the total is odd return false; otherwise let target = total / 2. Keep a boolean array reach of size target + 1 with reach[0] = true. For each number, iterate sums from target down to the number and set reach[s] |= reach[s - num]; iterating downward ensures each item is used at most once. Return reach[target].
time O(n · total)space O(total)
Alternative approaches
- Represent reachable sums as a big integer bitset and shift-or each number for a large constant-factor speedup. Exhaustive subset search is O(2^n).
Code it yourself
Solve in
Hints: