1. One-Liner
Subset sum asks whether a subset of given numbers can sum to T; the 0/1 version is a boolean knapsack on the sum dimension.
2. The Problem It Solves
Partition problems, payment exactness, and feasibility checks reduce to: is there S ⊆ A with ∑S = T? The DP tracks reachable sums using each number at most once.
3. The Core Idea
Process numbers; dp[s] means sum s is reachable. For each x, update dp backwards on s to avoid reusing the same element in one step—same trick as 0/1 knapsack.
4. How It Works (Step-by-Step)
| Step | What Happens | |
|---|---|---|
| 1 | dp[0]=true, others false | |
| 2 | For each value x, for s from T down to x | |
| 3 | `dp[s] | = dp[s-x]` |
| 4 | Answer dp[T] |
5. Dry Run Example
{3, 34, 4, 12, 5, 2}, T=9: subset {4,5} works → true.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n·T) |
| Bitset | Often speeds up in practice |
7. Where It Is Used
| Domain | Use |
|---|---|
| Scheduling | Exact resource hit |
| Crypto (toy) | Knapsack-style constructions |
8. Interview Tips
Relate to partition equal subset; discuss counting vs existence variants.
9. Comparison with Other Algorithms
| Variant | DP |
|---|---|
| Unbounded | Forward loop on sum |
| 0/1 subset | Backward loop |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n·T) |
| Space | O(T) |
Implementation Example (PYTHON)
def is_subset_sum(nums: list[int], target: int) -> bool:
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for s in range(target, x - 1, -1):
if dp[s - x]:
dp[s] = True
return dp[target]