Knapsack Variants and Subset Sum

Knapsack problems are notorious for a reason: the recurrences all look the same, and the differences live entirely in loop direction and loop nesting. Four one-line variations produce four different answers, and if you cannot derive which is which you will guess wrong under pressure.

This page is about deriving them. Two rules cover everything:

Loop direction decides whether an item can be reused. Descending over capacity means each item is used at most once (0/1). Ascending means each item can be used unlimited times (unbounded).

Loop nesting decides whether order matters. Items outer, capacity inner gives combinations (order-blind). Capacity outer, items inner gives permutations (order counted).

What you’ll learn

• Why a 1D array suffices, and what the descending loop is actually protecting.
• The 0/1 versus unbounded distinction, derived rather than memorised.
• Why LC 518 and LC 377 have the same recurrence and different loop nesting.
• The transform that turns “assign + and - signs” into a subset-sum problem.
• Three real LeetCode problems solved in the browser: 416, 494, 518.

The cue

You are looking at a knapsack when…

• You must choose a subset hitting an exact total, or maximise a value under a capacity — 416, 494, 474, 1049.
• Each item is take it or leave it, once — that is 0/1.
• Items may be reused without limit — that is unbounded: 518, 377, 322, 279.
• “Count the ways” to reach a target — 494, 518, 377.
• “Can it be partitioned into equal halves”, or “minimise the difference” — 416, 1049, which are subset-sum in disguise.

The anti-cue: if you must also report the chosen items, the 1D array has thrown that information away — keep the 2D table, or reconstruct by walking it backwards.

Visual intuition

The 2D table is the honest starting point, so it is worth watching one get filled before collapsing it. Each cell asks the same question — take this item, or skip it? — and the arrows show which two cells the answer comes from.

dp0/1 knapsack: every cell is max(skip = above, take = above-and-left-by-w)capacity 7, four items

rows: items consideredcols: capacity

1def knapsack(weights, values, cap):2    n = len(weights)3    dp = [[0] * (cap + 1) for _ in range(n + 1)]4    for i in range(1, n + 1):5        wt, val = weights[i - 1], values[i - 1]6        for c in range(cap + 1):7            dp[i][c] = dp[i - 1][c]              # skip item i8            if wt <= c:                          # can it fit?9                dp[i][c] = max(dp[i][c],10                               dp[i - 1][c - wt] + val)   # take it11    return dp[n][cap]

base caseRow 0 means "no items available", so every capacity yields value 0. Each later row adds exactly one item to the pool — the row index is *how many items you are allowed to consider*, not which item you took.

Play‹›1/38⟲

Look at where each cell reads from: dp[i-1][c] directly above (skip the item) and dp[i-1][c - w] up and to the left (take it). Both sources are in the PREVIOUS row -- which is what the one-array version has to preserve, and why it iterates capacity descending.

From 2D to 1D

The honest starting point is a 2D table: dp[i][c] is the answer using the first i items with capacity c.

$dp[i][c] = \max\big(dp[i-1][c],\ dp[i-1][c - w_i] + v_i\big)$

Every row depends only on the row above, so the table collapses to a single array. But collapsing introduces a hazard, and that hazard is the whole subject:

Why 0/1 knapsack iterates capacity DESCENDING

With one array, dp[c - w] is either “the previous row” (item not yet used) or “this row” (item already used), depending on whether you have overwritten it yet.

• Descending c: when you read dp[c - w], that smaller index has not been updated this round, so it still represents the previous row. The item is used at most once. This is 0/1.
• Ascending c: dp[c - w] has already been updated this round, so it may already include the current item — which lets the item be used again. This is unbounded.

One character of difference is the entire distinction between the two classic knapsacks. Derive it from “has this index been overwritten yet?” and you never have to remember it.

knapsack_directions.py

# 0/1 -- each item at most once: capacity DESCENDING
def can_reach_01(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for n in nums:
        for c in range(target, n - 1, -1):        # descending
            if dp[c - n]:
                dp[c] = True
    return dp[target]
 
 
# UNBOUNDED -- each item any number of times: capacity ASCENDING
def count_ways_unbounded(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:                            # items OUTER
        for a in range(coin, amount + 1):         # ascending
            dp[a] += dp[a - coin]
    return dp[amount]
 
 
print(can_reach_01([1, 5, 11, 5], 11))            # True
print(count_ways_unbounded([1, 2, 5], 5))         # 4

The inner loop’s lower bound (n - 1 or coin) simply avoids negative indices — a capacity below the item’s weight cannot fit it at all.

Combinations versus permutations

This is the second rule, and the one that silently produces wrong answers because both versions run fine.

	Loop nesting	Counts	coins=[1,2], amount=3
Combinations (518)	items outer, capacity inner	order ignored	{1,1,1}, {1,2} = 2
Permutations (377)	capacity outer, items inner	order counted	1+1+1, 1+2, 2+1 = 3

Why the nesting decides it

With items outer, the algorithm finishes with coin 1 before it ever considers coin 2. Any solution it builds therefore uses coins in that fixed order, so 1+2 and 2+1 are the same path and are counted once. That is combinations.

With capacity outer, at each amount you try every coin as the last one added. Reaching 3 via “…then a 1” and via “…then a 2” are separate paths, so 1+2 and 2+1 are both counted. That is permutations.

Nothing else changes — same recurrence, same dp[0] = 1, same ascending inner loop. Only the two for lines swap. Note that LC 377 is titled “Combination Sum IV” but actually counts permutations, which is a genuinely misleading name and a common trap.

The sign-assignment transform

LC 494 asks how many ways to put + or - before each number so the total equals target. That looks unlike a knapsack until you split the numbers into the positive set P and the negated set N:

$\text{sum}(P) - \text{sum}(N) = \text{target}, \qquad \text{sum}(P) + \text{sum}(N) = \text{total}$

Adding the two equations:

$\text{sum}(P) = \frac{\text{total} + \text{target}}{2}$

So the question becomes “how many subsets sum to that value?” — a standard 0/1 counting knapsack. Two feasibility checks fall straight out of the algebra:

• If total + target is odd, no integer subset sum exists, so the answer is 0.
• If abs(target) > total, the target is unreachable, so the answer is 0.

Zeros make this problem interesting

A 0 can take either sign and still contribute nothing, so it doubles the number of ways. The subset-sum formulation handles this automatically: dp[s] += dp[s - 0] is dp[s] += dp[s], which doubles every count.

nums = [1, 0], target = 1 gives 2 — +1+0 and +1-0. And nums = [0, 0], target = 0 gives 4, since each zero has two sign choices. A solution that special-cases zeros, or dismisses them as irrelevant, gets both wrong. This is a good example of a transform being not just shorter but safer.

Variant	Loop direction	Loop nesting	Problem
0/1: can we hit target?	descending	items outer	416
0/1: count subsets	descending	items outer	494
0/1: maximise value	descending	items outer	474
Unbounded: count combinations	ascending	items outer	518
Unbounded: count permutations	ascending	capacity outer	377
Unbounded: minimise count	ascending	either — min is order-blind	322 · 279

Dry run

Subset sum (LC 416’s core) — nums = [1, 5, 11, 5], target = 11, capacity descending. dp[c] means “some subset reaches exactly c”. Written as 1/0 for readability:

after item	dp[0..11]	newly reachable
— (init)	1 0 0 0 0 0 0 0 0 0 0 0	only 0, from the empty subset
1	1 1 0 0 0 0 0 0 0 0 0 0	1
5	1 1 0 0 0 1 1 0 0 0 0 0	5, 6
11	1 1 0 0 0 1 1 0 0 0 0 1	11 → the answer is already True
5	1 1 0 0 0 1 1 0 0 0 1 1	10 (= 5 + 5, using both fives)

• Each item adds only offsets of what was already reachable. After 5, index 6 lights up because index 1 was set — that is dp[c] |= dp[c - n], and it is why this is one array rather than a set of sums.
• The second 5 is a distinct item, and 10 proves it. Index 10 becomes reachable only on the last pass, using both fives. Deduplicating the input would be wrong here.
• Nothing is ever cleared. Once a capacity is reachable it stays reachable, so the array is monotone in time. That is what makes the boolean version safe to short-circuit on dp[target].

The direction bug, in the smallest case that shows it — nums = [2], target = 4:

loop direction	trace	dp[4]	means
descending 4 → 2	dp[4] |= dp[2] (still False), then dp[2] |= dp[0] → True	False	correct 0/1: one 2 cannot make 4
ascending 2 → 4	dp[2] |= dp[0] → True, then dp[4] |= dp[2] → True	True	unbounded: the 2 was reused

One character of loop direction, two different problems. The rule to derive rather than memorise: when you read dp[c - w], has this round already written it? Descending says no (so it is the previous row, item unused); ascending says yes (so the item may already be in there).

Combinations versus permutations — coins = [1, 2], amount = 3:

nesting	dp[0..3]	dp[3]
items outer (LC 518)	1 1 2 2	2 — {1,1,1}, {1,2}
capacity outer (LC 377)	1 1 2 3	3 — 1+1+1, 1+2, 2+1

Same recurrence, same dp[0] = 1, same ascending inner loop. Only the two for lines swap, and dp[2] is even identical in both — the divergence appears only at 3, which is why a small test case can pass with the wrong nesting.

Complexity

Let n be the number of items and C the capacity or target.

Variant	Time	Space
2D table (any variant)	$O(nC)$	$O(nC)$
1D rolling array	$O(nC)$	$O(C)$
Subset sum / partition (LC 416)	$O(nC)$	$O(C)$ — one boolean array
Coin change, min coins (LC 322)	$O(nC)$	$O(C)$
Count combinations / permutations (518, 377)	$O(nC)$	$O(C)$
Target sum via sign transform (LC 494)	$O(n \cdot \frac{S + T}{2})$	$O(S)$
Bitset subset sum	$O(nC / 64)$	$O(C / 64)$

$O(nC)$ is pseudo-polynomial, and that matters

The bound is polynomial in the value $C$, not in its number of digits — so a target of $10^9$ is intractable even with 3 items, while a target of 1000 with 200 items is instant. Knapsack is NP-hard; these DPs are efficient only because interview constraints keep $C$ small. When asked “what if the target is $10^{12}$?”, the answer is that this approach dies and you need meet-in-the-middle ($O(2^{n/2})$), branch and bound, or an approximation — not a bigger array.

Python’s arbitrary-precision integers make the bitset trick a genuine one-liner for boolean subset sum: keep mask = 1, and per item do mask |= mask << n. Then mask >> target & 1 is the answer, roughly 64× faster than the loop. Worth mentioning; it does not generalise to counting or maximising.

The variant map

Problem	Which knapsack	The one thing that changes
LC 416 Partition Equal Subset Sum	0/1, boolean	odd total → immediately False; target is total // 2
LC 494 Target Sum	0/1, counting	the sign transform: find subsets summing to (total + target) // 2; reject if that is odd or negative
LC 474 Ones and Zeroes	0/1, two capacities	dp[m][n], both dimensions descending
LC 322 Coin Change (min coins)	unbounded, minimising	dp[a] = min(dp[a], dp[a-c] + 1), init inf, dp[0] = 0
LC 518 Coin Change II	unbounded, counting combinations	items outer
LC 377 Combination Sum IV	unbounded, counting permutations	capacity outer — despite the problem’s name
LC 279 Perfect Squares	unbounded, minimising	the items are $1, 4, 9, \dots$ generated, not given
LC 1049 Last Stone Weight II	0/1, maximising	minimise the difference = get as close to total // 2 as possible
Bounded knapsack (k copies)	between the two	binary-split each item into $1, 2, 4, \dots$ copies, then run 0/1
Maximise value, not reachability	0/1 with values	dp[c] = max(dp[c], dp[c-w] + v) — same directions apply
Which items were chosen	any	keep the 2D table and walk backwards, or store a parent per cell; the 1D array throws that information away

Practice — real LeetCode problems

LC 416 — Partition Equal Subset Sum · Medium

Problem. Given an array of positive integers, decide whether it can be split into two subsets with equal sums.

Constraints. 1 <= len(nums) <= 200, 1 <= nums[i] <= 100.

Examples. [1,5,11,5] gives True ([1,5,5] and [11]) · [1,2,3,5] gives False · [1,1] gives True

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two equal subsets means each sums to total / 2, so this is exactly subset sum: can any subset reach that target?

Time $O(n \cdot \text{target})$, at most $200 \times 10000$ here. Space $O(\text{target})$.

This is pseudo-polynomial: linear in the numeric value of the sum, not in the number of bits needed to write it. Subset sum is NP-complete in general, and this DP is only efficient because the constraints bound the sum. Saying so shows you know why the approach works here rather than always.

• Odd total is an instant False — [1,2,3,5] sums to 11.
• dp[0] = True is the empty subset; without it nothing is ever reachable.
• Descending keeps it 0/1. [2,2,3,5] (total 12, target 6) is the discriminating case: no subset makes 6, but an ascending loop would reuse a 2 three times and wrongly return True.

A Python shortcut worth mentioning: a set of reachable sums, reachable |= {r + n for r in reachable}, is shorter and often faster in practice. Faster still is the bitset trick — bits |= bits << n, then test bit target — because Python’s big integers do the shifting in C.

Follow-ups you should expect: “Return the actual subsets?” — keep the 2D table and walk backwards. “Minimise the difference between the two subsets (LC 1049)?” — find the largest reachable sum at most total // 2; the answer is total - 2 * best. “Partition into k equal subsets (LC 698)?” — much harder, backtracking with pruning. “Why not greedy?” — taking the largest first fails on [1,5,11,5].

LC 494 — Target Sum · Medium

Problem. Assign + or - to each number in nums so the resulting expression equals target. Return the number of ways.

Constraints. 1 <= len(nums) <= 20, 0 <= nums[i] <= 1000, 0 <= sum(nums) <= 1000, -1000 <= target <= 1000.

Examples. nums = [1,1,1,1,1], target = 3 gives 5 · nums = [1], target = 1 gives 1 · nums = [1], target = 2 gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The transform is the whole solution. Splitting into positives P and negatives N gives sum(P) - sum(N) = target and sum(P) + sum(N) = total, so sum(P) = (total + target) / 2. Counting sign assignments becomes counting subsets with that sum.

Time $O(n \cdot \text{subset})$. Space $O(\text{subset})$.

Both guards come straight from the algebra:

• (total + target) % 2 — a non-integer subset sum is impossible. ([1], 2) hits this: (1 + 2) / 2 = 1.5.
• abs(target) > total — unreachable even using every number with one sign. Without this guard subset goes negative, [0] * (subset + 1) produces an empty list, and the indexing fails.

The zero cases are the reason to trust the algebra:

• ([1,0], 1) gives 2. Here subset = 1. Processing the 0, the inner loop runs dp[s] += dp[s - 0], i.e. dp[s] += dp[s], doubling every count. Correct: +1+0 and +1-0.
• ([0,0], 0) gives 4. Two zeros, two sign choices each: $2^2 = 4$. The doubling happens twice.

Follow-ups you should expect: “Do it with a memoised recursion instead?” — dfs(index, running_sum) with lru_cache; $O(n \cdot \text{sum})$ states, and arguably easier to derive under pressure, so it is worth offering. “Why the two guards?” — explain them from the algebra. “Negative numbers in nums?” — the constraints forbid it; with negatives the reachable range shifts and you would offset the dp indices. “Reconstruct one valid assignment?” — keep the 2D table and backtrack.

LC 518 — Coin Change II · Medium

Problem. Given coin denominations and an amount, return the number of combinations that make up that amount. You have an infinite supply of each coin, and combinations differing only in order count once.

Constraints. 1 <= len(coins) <= 300, 1 <= coins[i] <= 5000, all coins distinct, 0 <= amount <= 5000.

Examples. amount = 5, coins = [1,2,5] gives 4 · amount = 3, coins = [2] gives 0 · amount = 0, coins = [7] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Both loop decisions matter here, and each encodes one requirement:

• Ascending amount — dp[a - coin] has already been updated this round, so it may already include this coin. That is exactly the unbounded supply.
• Coins outer — solutions are built in a fixed coin order, so 1+2 and 2+1 are the same path. That is combinations, not permutations.

Time $O(\text{coins} \times \text{amount})$. Space $O(\text{amount})$.

(3, [1,2]) giving 2 is the discriminating case. The combinations are {1,1,1} and {1,2}. Swap the loops — amount outer, coins inner — and you get 3, because 1+2 and 2+1 become distinct. That answer is correct for LC 377 and wrong here, and the code looks equally reasonable either way.

(0, [7]) giving 1 follows from dp[0] = 1: the empty selection is a valid way to make zero. Easy to dismiss as a technicality, but it is also the base case the whole recurrence builds on.

The last case, (500, [1,2,5]) giving 12701, confirms the arithmetic scales rather than merely passing the tiny examples.

Follow-ups you should expect:

• “Count permutations instead (LC 377)?” Swap the loops: amount outer, coins inner. Same recurrence, same base case.
• “Minimum number of coins (LC 322)?” Change the recurrence to dp[a] = min(dp[a], dp[a - coin] + 1), with dp[0] = 0 and the rest float("inf"). Loop order does not matter there, because min is order-blind — a nice contrast worth pointing out.
• “Each coin usable at most once?” Iterate the amount descending, making it 0/1.
• “Which coins were used?” The 1D array has discarded that; keep the 2D table.
• “Very large amounts?” The DP is pseudo-polynomial; for huge amounts with few coins, generating functions or matrix exponentiation are the theoretical routes.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1049 is the reframing worth practising

Last Stone Weight II sounds like a simulation: smash two stones, keep the difference, repeat. It is not.

Every smashing sequence amounts to assigning each stone a + or - sign, so the final weight is abs(sum(P) - sum(N)). Minimising that means getting sum(P) as close to total / 2 as possible — subset sum again. Find the largest reachable sum best <= total // 2, and the answer is total - 2 * best.

The pattern: when a problem describes a process, ask what quantity the process actually determines. It often collapses to a partition or a subset sum, and the simulation was a red herring.

7 problems

0 easy7 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○322Coin ChangemediumMinimisation, so loop order is irrelevantNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemicrosoftbytedance
• ○377Combination Sum IVmediumAmount outer = **permutations**, despite the titleBlind 75
• ○416Partition Equal Subset SummediumBoolean 0/1 subset-sum to `total // 2`NeetCode 150
• ○474Ones and Zeroesmedium0/1 knapsack with **two** capacities -- both loops descending
• ○494Target SummediumAlgebra turns signs into subset-sum; zeros double the countNeetCode 150
• ○518Coin Change IImediumCoins outer + ascending = unbounded **combinations**NeetCode 150
• ○1049Last Stone Weight IImediumLargest reachable sum at most `total // 2`; answer is `total - 2 * best`

Interview follow-ups

They ask	What they’re checking	The answer
“Why descending for 0/1?”	Whether you derived it	Descending means dp[c - w] has not been overwritten yet, so it still represents the previous row — item used once
“Why does loop order change the count?”	The subtlest point	Items outer fixes a build order (combinations); capacity outer tries every item last (permutations)
“Is this polynomial?”	Precision	Pseudo-polynomial — linear in the numeric target, exponential in its bit length; subset sum is NP-complete generally
“How do you handle zeros in 494?”	Care	The subset-sum transform handles them automatically: dp[s] += dp[s] doubles the count
“Recover the chosen items?”	Limits of the optimisation	The 1D array cannot; keep the 2D table and walk back
“Two capacities (LC 474)?”	Generalisation	A 2D dp over both budgets, with both loops descending
“Does loop order matter for LC 322?”	Depth	No — min is order-blind, unlike counting

Edge-case checklist

• Odd total (LC 416) — instant False.
• Single element — [1] cannot be partitioned.
• amount = 0 (LC 518) — exactly one way (take nothing); tests dp[0] = 1.
• Target unreachable — (3, [2]) gives 0.
• abs(target) > total (LC 494) — guard before computing subset, or the array size goes negative.
• (total + target) odd (LC 494) — return 0.
• Zeros in the array (LC 494) — each doubles the count; ([0,0], 0) gives 4.
• Coin larger than the amount — the inner loop’s lower bound skips it safely.
• All elements equal — [100,100] partitions; [1,1] too.
• Large amounts — (500, [1,2,5]) checks the arithmetic scales.

Self-check

pch.quizTag Knapsack variants — self-check

1. In the one-array 0/1 knapsack, why must the capacity loop run descending?

   A For cache efficiency B So that when you read dp[c - w], that index has not been overwritten this round — it still represents the previous row, so the item is used at most once C Because dp[0] must stay True D To avoid negative indices
   pch.quizShowAnswer

   B — So that when you read dp[c - w], that index has not been overwritten this round — it still represents the previous row, so the item is used at most once — Derive it from 'has this index been written yet this round?' rather than memorising. Ascending makes dp[c - w] already include the current item, which is exactly the unbounded knapsack.

2. `nums = [2]`, `target = 4`. What do the two loop directions give?

   A Both False B Descending gives False (correct 0/1 — one 2 cannot make 4); ascending gives True, because the single 2 gets reused C Both True D Descending gives True, ascending gives False
   pch.quizShowAnswer

   B — Descending gives False (correct 0/1 — one 2 cannot make 4); ascending gives True, because the single 2 gets reused — This is the smallest input that separates the two, and worth keeping as a test. On [1,5,11,5] both directions happen to answer True, which is why the bug hides.

3. LC 518 counts combinations, LC 377 counts permutations. What is the difference in code?

   A A different recurrence B Only the loop nesting: items outer counts combinations; capacity outer counts permutations, because at each amount you try every coin as the last one added C One uses a 2D table D One initialises dp[0] = 0
   pch.quizShowAnswer

   B — Only the loop nesting: items outer counts combinations; capacity outer counts permutations, because at each amount you try every coin as the last one added — Same recurrence, same dp[0] = 1, same ascending inner loop. On coins [1,2] and amount 3 the answers are 2 versus 3 — but dp[2] is identical in both, so a small test can pass with the wrong nesting.

4. How does LC 494 (put + or − before each number to hit `target`) become a knapsack?

   A It cannot; it needs backtracking B Split into the positive set P and negated set N: P − N = target and P + N = total, so P = (total + target) / 2 — count 0/1 subsets summing to that, rejecting non-integer or negative results C Take absolute values and run unbounded knapsack D Sort the numbers and greedily assign signs
   pch.quizShowAnswer

   B — Split into the positive set P and negated set N: P − N = target and P + N = total, so P = (total + target) / 2 — count 0/1 subsets summing to that, rejecting non-integer or negative results — The parity and range guards are half the marks: if total + target is odd, or the required sum is negative, the answer is 0 with no DP at all.

5. The interviewer says the target is now 10^12. What happens to your O(nC) solution?

   A It still works; just use a dict instead of a list B It dies — O(nC) is pseudo-polynomial, i.e. polynomial in the value of C rather than its digit count. Knapsack is NP-hard; you would need meet-in-the-middle O(2^(n/2)), branch and bound, or an approximation C Switch to a 2D table D It becomes O(n log C)
   pch.quizShowAnswer

   B — It dies — O(nC) is pseudo-polynomial, i.e. polynomial in the value of C rather than its digit count. Knapsack is NP-hard; you would need meet-in-the-middle O(2^(n/2)), branch and bound, or an approximation — Recognising that these DPs are efficient only because interview constraints keep C small is the difference between reciting the recurrence and understanding it.

6. The follow-up asks WHICH items were selected, not just the best value. What changes?

   A Nothing — read it off the 1D array B The 1D array has thrown that information away; keep the 2D table and walk backwards (or store a parent per cell), trading O(C) space back up to O(nC) C Sort items by value/weight and re-run D Run the DP twice
   pch.quizShowAnswer

   B — The 1D array has thrown that information away; keep the 2D table and walk backwards (or store a parent per cell), trading O(C) space back up to O(nC) — The space optimisation is not free: collapsing rows destroys the decision history. Naming that trade-off unprompted is what the question is testing.

Recall card

• Cue — pick a subset of items to hit or maximise against a capacity: subset sum, partition, coin change, target sum, “can these be split evenly”.
• 2D honest form — dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v). Both sources are in the previous row; that is what the 1D collapse must preserve.
• 0/1 → capacity DESCENDING. Unbounded → capacity ASCENDING. Derive it from “has this index been written this round?”
• Combinations → items outer. Permutations → capacity outer. LC 518 vs LC 377, and LC 377’s name lies.
• Booleans — dp[0] = True, dp[c] |= dp[c-n]. Counting — dp[0] = 1, dp[a] += dp[a-c]. Minimising — dp[0] = 0, rest inf.
• Sign transform (LC 494) — target subset is (total + target) // 2; reject odd or negative.
• Cost — $O(nC)$ time, $O(C)$ space, pseudo-polynomial: fine for $C \le 10^5$, hopeless for $10^{12}$.
• Recovering the chosen items needs the 2D table back.

Recap

• The 2D knapsack table collapses to 1D because each row depends only on the row above — and collapsing is what makes loop direction significant.
• Loop direction decides reuse. Descending over capacity gives 0/1 (each item once); ascending gives unbounded. Derive it from “has this index been overwritten this round?”.
• Loop nesting decides ordering. Items outer gives combinations; capacity outer gives permutations. LC 518 and LC 377 differ only in this, and LC 377’s title says “combination” while it counts permutations.
• Loop order is irrelevant for minimisation (LC 322), because min is order-blind. Only counting cares.
• dp[0] is the base case everything rests on — True for reachability, 1 for counting, 0 for minimisation.
• Algebra beats case analysis. The sum(P) = (total + target) / 2 transform turns sign assignment into subset sum and handles zeros for free.
• These DPs are pseudo-polynomial — efficient only because the constraints bound the target.

Next: Classic DP — LIS, LCS and Edit Distance — the sequence-alignment family, where the state is a pair of indices rather than a capacity.