Unbounded Knapsack and Coin Change II

In Unbounded Knapsack, each item can be taken any number of times (unlike 0/1 knapsack where each item is used at most once). The state definition is the same — dp[c] = maximum value achievable with capacity c — but the iteration direction changes. Because items are reusable, when we update dp[c] we want to allow the current item to be used again, so we iterate capacity left to right (forward).

Recall that in 0/1 knapsack we iterated right to left to prevent reuse. In unbounded knapsack we do the opposite: iterate left to right. When computing dp[c], dp[c-w] has already been updated in the current pass — meaning item i was possibly already included. This is exactly what we want: item i can be added again to a solution that already contains item i.

Coin Change II asks: given coin denominations and an amount, count the number of distinct ways to make that amount (each coin can be used unlimited times). This is an unbounded knapsack variant where instead of maximising value, we count combinations. Define dp[c] as the number of ways to make amount c. Base case: dp[0] = 1 (one way to make 0: take nothing).

For each coin, iterate amounts left to right and accumulate: dp[c] += dp[c - coin]. The base case dp[0] = 1 seeds the count. Note the outer loop is over coins and the inner loop is over amounts — this naturally gives combination counts (not permutations), because each coin denomination is considered exactly once as an outer pass.

The order of the loops matters critically. If we put amount in the outer loop and coin in the inner loop, we count permutations (order matters). For amount=5 with coins [1,2]: 1+2+2 and 2+1+2 are counted separately. If we put coin in the outer loop, we count combinations (order does not matter): 1+2+2 and 2+1+2 are the same. Coin Change II asks for combinations, so coin is the outer loop.

Another classic unbounded knapsack problem: given a rod of length n and prices for each rod length 1 to n, find the maximum revenue by cutting the rod optimally. Each piece of length l can be sold for price[l], and pieces can be reused (the rod can be cut into multiple pieces of the same length). This maps directly to unbounded knapsack with W = n and items being the different cut lengths.

Coin Change I (a different problem) asks for the minimum number of coins to make a target amount. Here dp[c] = minimum coins to make amount c. Recurrence: dp[c] = min(dp[c], dp[c - coin] + 1). Initialise all entries to inf except dp[0] = 0. This is also unbounded (coins can be reused), so iterate left to right. Return dp[amount] if finite, else -1.

The three unbounded knapsack variants use different operations on dp[c-coin]: Maximise value: dp[c] = max(dp[c], dp[c-w] + v); initialise to 0. Minimise cost: dp[c] = min(dp[c], dp[c-coin] + 1); initialise to inf, dp[0]=0. Count ways: dp[c] += dp[c-coin]; initialise to 0, dp[0]=1. Recognising which variant applies is half the battle in interview problems.

All unbounded knapsack variants run in O(n × W) time and O(W) space where n is the number of item types and W is the target amount. For coin problems, n is the number of coin denominations. In interviews, state the variant (max/min/count), write the 1D DP, and be explicit about whether the outer loop is coins or amount — examiners know this distinction tests deep DP understanding.

Use these signals to identify which variant applies: unlimited reuse → unbounded (forward iteration); each item exactly once → 0/1 (backward iteration); problem says 'any number of times', 'infinite supply', or 'reuse allowed' → unbounded. Examples: coin change, rod cutting, integer break — all unbounded. Subset sum, partition, 0/1 knapsack — 0/1. Getting this wrong causes wrong answers that are hard to debug.

Integer Break (LeetCode 343): split an integer n into at least 2 positive integers to maximise their product. This is an unbounded knapsack where 'items' are the integers 2 through n-1. Define dp[i] = max product of integers summing to i. For each item j from 2 to i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). This shows how the unbounded pattern generalises beyond the coin context.

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

In this lesson you learned: unbounded knapsack iterates capacity left to right to allow item reuse, Coin Change II counts combinations by putting coin in the outer loop, and the three variants — maximise, minimise, count — differ only in the DP operation and initialisation. Next up we use the 0/1 knapsack to solve Partition Equal Subset Sum.