Unbounded Knapsack: Combinations vs Permutations

Unbounded knapsack is take-or-skip where taking an item doesn't use it up. The counting version is where it gets tricky: "how many ways make this amount?" Before you write any code, you have to decide whether 5 + 5 + 2 and 2 + 5 + 5 are the same way (a combination) or different ways (a permutation). Coin Change II (LC 518) and Combination Sum IV (LC 377) are the same problem except for that one decision.

The idea#

If the state is only the amount left, ways(amount) = sum(ways(amount - c) for c in coins) counts every ordering separately. It tries every coin as the first coin, then every coin as the second, and so on. That's correct for permutations and wrong for combinations.

To count each multiset once, add the coin index to the state and only allow coins from index i onward:

• Take coin i: ways(amount - coins[i], i). Stay on i, because it can be used again.
• Skip coin i: ways(amount, i + 1). Never come back to it.

Why does this work? Every combination is now built in one canonical order (all of coin 0, then all of coin 1, ...), so it's counted exactly once.

How to spot it#

Most of the work is reading the question carefully. Look for these signals.

• "Unlimited supply", "each coin may be used any number of times", "infinite".
• "Number of combinations" (order doesn't matter) vs "number of possible combinations" where the examples list (1, 2) and (2, 1) separately (order matters). Read the examples to decide.
• Min-count versions don't care about order; see Min/Max to a Target.

Template#

Here is the take-or-skip recursion from above, which counts combinations because the item index is part of the state.

ways(rem, i):
    if rem == 0:
        return 1                      # built the amount exactly
    if rem < 0 or i == number of items:
        return 0
    take = ways(rem - size[i], i)     # reuse allowed: stay on i
    skip = ways(rem, i + 1)           # done with item i for good
    return take + skip
memoize ways on (rem, i)
answer: ways(target, 0)

Bottom-up: the loop order decides#

If you build the answer bottom-up instead, there is no index in the state to control order. In a 1-D table dp[a] (ways to make a, with dp[0] = 1), the same choice becomes the loop order.

combinations:                         # item loop outside
    for each item c:
        for a from c up to target:
            dp[a] += dp[a - c]
permutations:                         # amount loop outside
    for a from 1 up to target:
        for each item x with x <= a:
            dp[a] += dp[a - x]

A tiny input shows the difference. With pieces [1, 2] and target 3:

With the item loop outside, by the time piece 2 is processed, piece 1 has already been placed everywhere it can go. So 2 can only come after 1s, never before. With the amount loop outside, every piece is tried as the last piece of every amount, so all orders are counted.

Pitfalls#

Each of these quietly changes which ways get counted.

• Using only the amount as the state when the problem wants combinations. 5,5,2 and 2,5,5 are counted as two ways.
• Moving to i + 1 after taking an item. That makes it 0/1 knapsack (each item at most once).
• Swapping the loops by accident in the bottom-up version. The code still runs and gives a plausible but wrong number.
• In the 1-D table, left-to-right capacity is what makes reuse possible. Right to left would be 0/1 knapsack.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

• 518. Coin Change II
• 377. Combination Sum IV
• 322. Coin Change
• 279. Perfect Squares

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Unbounded = take and stay on the same item; skip = move on for good.
• Combinations need a canonical order, which the item index provides.
• Bottom-up: coins outer gives combinations, amount outer gives permutations.
• Check the examples to see whether reorderings are counted.