Lesson 30.2 · Knapsack DP
Subset Sum and Its Disguises
Many problems become "can (or how many ways can) a subset reach sum S?" after a little algebra.
12 min
Think of it like this
Splitting a bag of coins between two friends as fairly as possible: if one friend's share is S, the other's is total − S, so you only need to know which sums a subset can make.
1.Three transformations
Equal partition: two equal halves exist ⇔ some subset sums to total / 2 (and total is even). Boolean knapsack: can[c] |= can[c − x].
Target sum with + and −: if P is the sum of the + numbers and N of the − numbers, P − N = target and P + N = total, so P = (total + target) / 2. Count subsets with sum P.
Last stone weight II: smashing stones in any order ends with |S₁ − S₂| for some split into two groups. Find the reachable subset sum closest to total / 2.
Quick check
nums = [1, 1, 1, 1, 1], target 3: what is P?
Remember
- Rewrite the goal as a subset sum.
- Boolean: OR. Counting: +.
- Check parity and range before dividing.
Common mistakes
- Forgetting that (total + target) must be even and non-negative.