L38 · DP VI — Unbounded Knapsack

Series: LeetCode — From Basics to Interview-Ready · Session 38 / 65 · Phase 2 · Dynamic programming

Prerequisites

L37 (0/1 knapsack) is mandatory — this session is defined as its opposite. If you cannot yet say "0/1 sweeps capacity backwards", stop and finish L37 first. Everything here is the same table with the inner loop reversed.

Watch first (skim before the session)

Why this session exists

Unbounded knapsack is 0/1's mirror image, and interviewers test whether you can tell them apart under pressure. The naked version — "items with weight and value, capacity W, each item usable unlimited times, maximise value" — is rare; the disguises are everywhere: Coin Change (fewest coins), Coin Change 2 (how many ways), Rod Cutting (best price to cut a rod), Combination Sum IV (count ordered ways to reach a target).

Two details carry this session. First: the single-character difference from 0/1 — the capacity loop runs forwards so dp[c-w] already includes the current item, making it reusable. Second, and subtler: for the counting variants, the order of the two loops decides whether you count combinations (item loop outside) or permutations (capacity loop outside). That loop-order distinction is a favourite senior-level probe.

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory, and note the one flipped line:

unbounded value :  for c from w to W:            # FORWARDS (reusable)
                        dp[c] = max(dp[c], dp[c-w] + v)
 
coin change min :  for c from coin to amount:    # FORWARDS
                        dp[c] = min(dp[c], dp[c-coin] + 1)

If the loop direction wobbles against L37, drill the pair: "one-of-each backwards, unlimited forwards."

From first principles

Unbounded value maximisation (the naked form):

def unbounded_knapsack(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for c in range(1, W + 1):
        for w, v in zip(weights, values):
            if w <= c:
                dp[c] = max(dp[c], dp[c - w] + v)   # reuse allowed: dp[c-w] may include this item
    return dp[W]
 
assert unbounded_knapsack([1, 3, 4], [15, 50, 60], 8) == 130   # 4+4 -> 60+60

Coin Change — the canonical disguise

Fewest coins to make an amount, coins reusable — unbounded knapsack minimising count.

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0                                 # 0 coins make amount 0
    for c in range(1, amount + 1):
        for coin in coins:
            if coin <= c:
                dp[c] = min(dp[c], dp[c - coin] + 1)   # forwards: reuse coins
    return dp[amount] if dp[amount] != INF else -1
 
assert coin_change([1, 2, 5], 11) == 3       # 5 + 5 + 1
assert coin_change([2], 3) == -1             # impossible
assert coin_change([1], 0) == 0

• Complexity: O(amount · len(coins)) time, O(amount) space.
• Follow-up: return the actual coins (parent pointers), or count the number of ways (Coin Change 2), which flips it to a counting problem with a loop-order subtlety.

Coin Change 2 — where loop order bites

Count the number of combinations of coins that make the amount. Coins outer, amount inner:

def coin_change_2(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1                                 # one way to make 0: take nothing
    for coin in coins:                        # coins OUTER  -> counts combinations
        for c in range(coin, amount + 1):     # forwards -> reusable
            dp[c] += dp[c - coin]
    return dp[amount]
 
assert coin_change_2(5, [1, 2, 5]) == 4      # {5},{2,2,1},{2,1,1,1},{1x5}
assert coin_change_2(3, [2]) == 0

If you swap the loops (amount outer, coins inner) you count permutations instead — [1,2] and [2,1] become distinct — which is Combination Sum IV, a different problem. This is the senior probe.

Memory hook

"Unlimited, sweep forwards — coins outside for combos, target outside for orders." The first clause pairs with L37's "one of each, sweep backwards." The second clause encodes the only genuinely tricky bit of this session — the counting loop order. Recite the full pair (L37 + L38) as one sentence and both knapsacks are locked.

What interviewers actually ask

• LC322 · Coin Change — Amazon, Google. Fewest coins for an amount. Probe: recognising unbounded knapsack, the forward loop, and the "impossible ⇒ -1" sentinel. Follow-up: reconstruct the coins, or handle huge amounts.
• LC518 · Coin Change 2 — Amazon. Count combinations. Probe: the coins-outer loop order and why it counts combinations not permutations. This is the discriminating question.
• LC377 · Combination Sum IV — Google. Despite the name, it counts permutations (ordered), so it's the capacity-outer twin of Coin Change 2. Probe: can you articulate that the loop order flips the meaning?
• LC279 · Perfect Squares — Amazon. Fewest perfect squares summing to n = Coin Change with coins = {1,4,9,16,...}. Probe: seeing the reduction, and the sqrt bound on the coin set.
• LC983 · Minimum Cost For Tickets — Google. An unbounded-flavoured DP over days with 1/7/30-day passes. Probe: state as cost-to-cover-up-to-day-i with reusable passes.
• LC518 vs LC377 side by side — interviewers sometimes ask both to see if you truly understand loop order versus having memorised one template.

Escalation ladder: fewest items (min) → count combinations → count permutations → reconstruct the multiset. The middle two are the same DP with the loops swapped — the whole point of the session.

Combination Sum IV — the loop-order twin

Plain words. Given distinct positive integers nums and a target, count the number of ordered sequences that sum to the target. The name says "combination"; the examples make clear it means permutations. That naming trap is deliberate on LeetCode's part and interviewers know it.

The insight. Everything about the array and the recurrence is identical to Coin Change 2. Only the nesting flips. Ask "how many ordered ways end with this number?" and you get a natural target-outer loop:

def combinationSum4(nums: list[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1                          # one ordered way to reach 0: the empty sequence
    for t in range(1, target + 1):     # TARGET outer -> order matters
        for x in nums:                 # every number gets a chance to be the LAST one
            if x <= t:
                dp[t] += dp[t - x]
    return dp[target]
 
assert combinationSum4([1, 2, 3], 4) == 7   # 1111,112,121,211,13,31,22

Compare it line by line with the combinations version and the only difference is which for is on the outside:

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                    # COINS outer -> order does not matter
        for t in range(c, amount + 1): # forward -> coin reusable
            dp[t] += dp[t - c]
    return dp[amount]
 
assert change(4, [1, 2, 3]) == 4            # 1111, 112, 22, 13

Seven versus four on the same inputs. That gap is the entire lesson, and being able to produce both numbers on demand is the cleanest way to prove you understand loop order rather than having memorised a template.

The follow-up they escalate to: "what if negative numbers were allowed?" Then sequences can be infinitely long (add +1 and -1 forever), the count is unbounded, and the DP has no well-founded ordering to recurse on. You would need an explicit length cap to make the question well posed — saying that is the expected answer.

def coin_change_with_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    choice = [None] * (amount + 1)
    for t in range(1, amount + 1):
        for c in coins:
            if c <= t and dp[t - c] + 1 < dp[t]:
                dp[t] = dp[t - c] + 1
                choice[t] = c
    # now reconstruct the coin multiset by walking choice backwards
    return None

Tradeoff

In practice

Making change is the textbook example, but the same DP powers cutting-stock optimisation (cut raw material into pieces to maximise value — Rod Cutting is literal unbounded knapsack) and billing/pass-selection systems that pick the cheapest combination of reusable passes to cover a period. Whenever a resource is available in unlimited units and you're optimising or counting ways to hit a target, unbounded knapsack is the engine.

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC322 Coin Change — unbounded min, the gateway.
2. LC518 Coin Change 2 — count combinations (coins outer).
3. LC377 Combination Sum IV — count permutations (target outer); feel the flip.
4. LC279 Perfect Squares — Coin Change with square coins.
5. LC983 Minimum Cost For Tickets — unbounded-flavoured day DP.
6. LC139 Word Break — unbounded reachability where the "coins" are dictionary words and the capacity axis is string position.
7. LC518 and LC377 back to back, from a blank file — write both in one sitting and confirm you get 4 and 7 on target 4 with {1,2,3}.

Spaced-repeat anchors: LC322 and LC518. LC322 carries the forward-loop minimum; LC518 carries the loop-order nuance that this entire session exists for. Re-solve both at +7d and again at +21d, and on the +21d pass write LC377 immediately afterwards to re-test the flip.