Knapsack Patterns (0/1, Unbounded, Subset-Sum)

Why knapsack gets its own subtopic

Knapsack isn't one problem — it's a family of recurrences that all share the same skeleton (items, a capacity/target dimension, a take-or-skip decision) but differ in one crucial constraint: can each item be used more than once? That single yes/no answer changes the loop direction in the space-optimized solution, and getting it backwards is the single most common silent bug in this entire topic — your code runs, returns a plausible-looking number, and is simply wrong.

Recognizing "this is a knapsack problem" is itself a skill: any problem that asks you to select a subset of items under a capacity/sum constraint while optimizing (or counting, or checking feasibility of) some value is a knapsack variant, even when it's disguised as partitioning, target-reaching, or "ways to form a sum."

0/1 Knapsack: each item used at most once

Problem shape: given items with weights and values, and a capacity W, choose a subset (each item taken 0 or 1 times) maximizing total value without exceeding W.

State: dp[i][w] = the best value achievable using only the first i items with capacity exactly (or at most) w.

Transition: for item i with weight wt and value val, you either skip it (dp[i-1][w]) or take it (dp[i-1][w - wt] + val, only valid if w >= wt) — take the max of the two. The critical detail: taking item i looks back at dp[i-1], the state before item i was considered, because you can't take the same item twice.

Unbounded Knapsack: unlimited reuse

Problem shape: identical to 0/1, except each item can be taken any number of times (e.g. coins, where you have infinite supply of each denomination).

Transition: taking item i now looks back at dp[i][w - wt] — the current row, not the previous one — because after taking one copy of item i, item i is still available for further use.

$$f_{i,j} = \max(f_{i-1,j},\ f_{i,j-w_i} + v_i)$$

The loop-order bug — the single most important detail in this subtopic

Both recurrences collapse to the same-looking 1-D space-optimized update:

f[j] = max(f[j], f[j - w] + v)

...but they are only correct if you iterate j in the right direction, and this is where almost every candidate who "sort of" understands knapsack gets tripped up:

	0/1 Knapsack	Unbounded Knapsack
Each item usable	Once	Unlimited times
1-D loop direction over capacity/target	Backward (capacity down to weight)	Forward (weight up to capacity)
Why	Prevents f[j - w] from having already been updated using item i in this same pass — it must still reflect the state before item i	You want f[j - w] to reflect an update from this same item, so item i can be reused
Canonical problems	Partition/subset-sum, 0/1 knapsack itself	Coin Change (both minimize-coins and count-ways variants), Perfect Squares

If you go backward for an unbounded problem, you silently cap every item at "used once" and undercount. If you go forward for a 0/1 problem, you silently allow infinite reuse and overcount. Neither throws an error — both just return a wrong number that looks reasonable, which makes this bug notoriously hard to catch by inspection alone. State the loop direction out loud and justify it every time you write a space-optimized knapsack in an interview; it signals you understand why, not just the template.

Subset-Sum and partition problems: knapsack in disguise

"Can this array be partitioned into two subsets with equal sum?", "count the subsets that sum to k", and "assign +/- signs to reach a target" are all the same 0/1 knapsack shape wearing different clothes — the "value" of each item is irrelevant; you only care about whether/how many ways a target sum is reachable using each element at most once.

The "assign +/- to reach a target" shape reduces to this exact subset-sum template with one bit of algebra: if P is the subset assigned + and N the subset assigned -, then P - N = target and P + N = total, so P = (total + target) / 2 — the problem becomes "how many subsets sum to P." Spotting this reduction is the problem; once you see it, the DP is routine.

2-D table vs. 1-D rolling array

	2-D table (dp[i][w])	1-D rolling array (dp[w])
Space	O(n × W)	O(W)
Clarity	Easier to derive correctly first — explicit "previous row" access matches the recurrence directly	Requires reasoning about loop direction (see above)
When to use in an interview	Derive here first if you're unsure	Convert to this once the recurrence is validated, as the space-optimization follow-up
Reconstructing the chosen items	Straightforward — walk back through both dimensions	Not possible without extra bookkeeping — the row history is gone

Complexity

For n items and capacity/target W: both 0/1 and unbounded knapsack are O(n × W) time. 0/1 knapsack space is O(n × W) unoptimized, O(W) with the rolling array. Unbounded knapsack space is the same. This is pseudo-polynomial — the runtime depends on the magnitude of W, not just the count of items, which is why knapsack problems often come with constraints like "sum of array ≤ 20000": that's your signal the intended solution is O(n × sum), not something faster.

Common pitfalls

• Wrong loop direction (covered above) — by far the most common bug, and the one to be most paranoid about.
• Off-by-one in the capacity dimension. dp arrays are almost always sized capacity + 1 to include index 0 (the "empty knapsack" / "sum of zero" state) as a real, reachable base case.
• Confusing "at most W" with "exactly W." Subset-sum-style problems usually want exactly a target sum, which means dp[0] = True/1 is your only valid seed — all other dp[s] for s > 0 start as False/0, not automatically reachable.
• Forgetting the odd-total short-circuit in equal-partition-style problems: if the total sum is odd, no equal partition can exist, and you should return early rather than running the DP at all.
• Confusing "counting ways" with "checking feasibility." A feasibility check uses booleans and OR (dp[s] = dp[s] or dp[s-num]); a counting variant uses integers and addition (dp[s] += dp[s-num]) — mixing these up (e.g. accidentally overwriting instead of accumulating) silently breaks counting problems like Coin Change II.
• Applying 0/1 loop direction to an unbounded problem "just to be safe." It isn't safe — it changes the answer. There is no universally-safe direction; the direction is determined entirely by whether items are reusable.