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

From 2D to 1D

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

$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:

# 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

# 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 - 1n - 1 or coincoin) 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.

The sign-assignment transform

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

$\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 + targettotal + target is odd, no integer subset sum exists, so the answer is 00.
• If abs(target) > totalabs(target) > total, the target is unreachable, so the answer is 00.

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) <= 2001 <= len(nums) <= 200, 1 <= nums[i] <= 1001 <= nums[i] <= 100.

Examples. [1,5,11,5][1,5,11,5] gives TrueTrue ([1,5,5][1,5,5] and [11][11]) · [1,2,3,5][1,2,3,5] gives FalseFalse · [1,1][1,1] gives TrueTrue

LC 494 — Target Sum · Medium

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

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

Examples. nums = [1,1,1,1,1], target = 3nums = [1,1,1,1,1], target = 3 gives 55 · nums = [1], target = 1nums = [1], target = 1 gives 11 · nums = [1], target = 2nums = [1], target = 2 gives 00

LC 518 — Coin Change II · Medium

Problem. Given coin denominations and an amountamount, 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) <= 3001 <= len(coins) <= 300, 1 <= coins[i] <= 50001 <= coins[i] <= 5000, all coins distinct, 0 <= amount <= 50000 <= amount <= 5000.

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

LeetCode problem set

Interview follow-ups

Edge-case checklist

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

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 minmin is order-blind. Only counting cares.
• dp[0]dp[0] is the base case everything rests on — TrueTrue for reachability, 11 for counting, 00 for minimisation.
• Algebra beats case analysis. The sum(P) = (total + target) / 2sum(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.