Equal Subset Partition
Hard · rating 1850 · Dynamic Programming
The first line has n. The second line has n positive integers. Print YES if they can be split into two groups with equal sums, otherwise NO.
Constraints: 1 ≤ n ≤ 200, 1 ≤ ai ≤ 100
Editorial
Approach
If the total is odd, it's impossible. Otherwise the question is whether some subset sums to total / 2 — a classic subset-sum DP. A reachable-sums bitset makes it fast: bit s is set when sum s is achievable, and adding a number x is a single shift-or (dp |= dp << x).
Why the bitset works
Shifting the whole set of reachable sums left by x and OR-ing it back records “every old sum, plus x” in one machine operation per number.
if total % 2: return 'NO'
dp = 1
for x in a: dp |= dp << x
return 'YES' if (dp >> total//2) & 1 else 'NO'Complexity
Time: O(n·sum / word). Space: O(sum).
Related problems
- Balanced Bracket Count — Hard
- Treasure Grid — Hard
- Word Break — Hard
- 0/1 Knapsack — Hard
- Coin Change (Count Ways) — Hard
- Decode Ways — Hard