Skip to content

144 — Coin Change II

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

144 — Coin Change II

LeetCode 518 · Medium. You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount cannot be made up by any combination of the coins, return 0. You may assume that you have an infinite number of each kind of coin.

🍽️ Intuition

This looks like its sibling, Coin Change (chapter 136), but it's asking a different question — not the fewest coins, but the number of distinct combinations, where order doesn't matter (a nickel-then-dime counts the same as a dime-then-nickel). That "order doesn't matter" detail is the whole difficulty: if you loop amount-first and coin-second, you'll count {1, 2} and {2, 1} as two different combinations. The fix is to think of it as a grid indexed by which coins you've considered so far (rows) and the running amount (columns) — decide, coin by coin, how many ways there are to hit each amount using only the coins considered up through that row. That two-axis "coins used so far x amount so far" state is what makes this a 2-D DP problem rather than the 1-D DP of the fewest-coins version.

🚩 Pattern-Recognition Cue

"Number of combinations to make an amount, coins reusable, order doesn't matter" is the unbounded-knapsack-counting tell: because combinations (not permutations) are being counted, the state needs two indices — how far through the list of coin denominations, and how much amount is left to cover — rather than amount alone.

🐢 Brute Force

Recurse over "coin index x remaining amount," at each step either using the current coin again (staying on the same index, since coins are unlimited) or moving on to the next denomination, with no memoization.

func changeBruteForce(_ amount: Int, _ coins: [Int]) -> Int {
    func waysFrom(_ index: Int, _ remaining: Int) -> Int {
        if remaining == 0 { return 1 }
        if remaining < 0 || index == coins.count { return 0 }

        let takeCoin = waysFrom(index, remaining - coins[index])   // reuse this same coin
        let skipCoin = waysFrom(index + 1, remaining)              // move to the next denomination
        return takeCoin + skipCoin
    }

    return waysFrom(0, amount)
}

// smoke test
print(changeBruteForce(5, [1, 2, 5]))   // 4
print(changeBruteForce(3, [2]))         // 0
print(changeBruteForce(0, [7]))         // 1

Big-O: O(2^(amount)) time in the worst case — every (index, remaining) pair branches two ways, and the same pairs are re-explored down many different decision sequences. O(amount) space for the recursion stack.

🚀 Optimal

Fill a (coins.count + 1) x (amount + 1) table where dp[i][j] is the number of ways to make amount j using only the first i coin denominations — row i either ignores the i-th coin entirely (inheriting row i-1) or uses at least one of it (looking back into row i itself, at a smaller amount).

func change(_ amount: Int, _ coins: [Int]) -> Int {
    let n = coins.count
    var dp = Array(repeating: Array(repeating: 0, count: amount + 1), count: n + 1)
    for i in 0...n {
        dp[i][0] = 1   // exactly one way to make amount 0: use no coins
    }

    guard n > 0 && amount > 0 else { return dp[n][amount] }

    for i in 1...n {
        for j in 0...amount {
            dp[i][j] = dp[i - 1][j]              // don't use coin i-1 at all
            if j >= coins[i - 1] {
                dp[i][j] += dp[i][j - coins[i - 1]]   // use one more of coin i-1
            }
        }
    }
    return dp[n][amount]
}

// smoke test — same cases as the brute force
print(change(5, [1, 2, 5]))   // 4
print(change(3, [2]))         // 0
print(change(0, [7]))         // 1

Big-O: O(n · amount) time, where n is the number of denominations — every cell is filled once from two already-known cells. O(n · amount) space for the dp table (collapsible to a single 1-D row of size amount + 1, since row i only ever reads row i-1 and itself).

🔑 The Key Insight

Both versions make the same choice at every (coin index, amount) pair — use the current denomination again, or move on to the next one — but the brute force treats every pair as fresh no matter how many decision paths reach it, so the same sub-totals are re-solved exponentially many times. The optimal version fills the table one coin-row at a time, so row i-1 is always a finished answer before row i needs it, and within row i, smaller amounts are finished before larger ones need them. Crucially, processing coins in the outer loop (rather than amount in the outer loop) is what prevents double-counting permutations as separate combinations — each combination is only ever built up in one canonical coin order.

🔗 Related Chapters

  • 2D Dynamic Programming — the "extra dimension of state" signal from chapter 27 applies here: the table isn't indexed by amount alone but by "amount x how many coin denominations have been considered," which is what correctly separates combinations from permutations.
  • Arrays and Strings — the dp table is a plain 2-D array filled row by row.

🧸 Memory Sentence

Coin Change II is unbounded knapsack counting combinations, not permutations — looping coins on the outside and amount on the inside ensures each combination is built in one fixed coin order, never double-counted.

✅ Check Your Understanding

  1. Why would swapping the loop order — amount on the outside, coins on the inside — cause {1, 2} and {2, 1} to be counted as two separate combinations for amount = 3, coins = [1, 2]?
  2. Trace change(5, [1, 2, 5]) by hand-filling row i = 2 (coins [1, 2] considered) of the table. What is dp[2][5], and which two coin combinations does it represent?
  3. Why does dp[i][j] += dp[i][j - coins[i-1]] read from row i (the current row) rather than row i-1, unlike the "don't use this coin" term which reads from row i-1?

⬅️ Previous: Best Time to Buy and Sell Stock with Cooldown · Next: Target Sum ➡️

Clone this wiki locally