Coin Change II

This is a counting problem, not a “does it fit” problem, so it needs combinations — order does not matter, 1+2 and 2+1 are the same combination. The trick that avoids double counting is to fix an order on the coins and decide, for each coin, how many times it appears, moving to the next coin only once the current one has been fully considered.

Brute Force Recursion

Time O(2^(amount + coins.length))Space O(coins.length + amount)

Process coins one at a time, in a fixed order. At each coin, either use it again (staying on the same coin, reducing the remaining amount) or move on to the next coin without using it. This ordering is exactly what prevents [1,2] and [2,1] from being counted as two different combinations.

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        def rec(i: int, remaining: int) -> int:
            if remaining == 0:
                return 1
            if i == len(coins) or remaining < 0:
                return 0
            use = rec(i, remaining - coins[i])
            skip = rec(i + 1, remaining)
            return use + skip
        return rec(0, amount)

Every unit of remaining can branch again, and the same (i, remaining) state is recomputed from scratch on every path that reaches it.

2-D DP Table (Bottom-Up)

OptimalTime O(coins.length · amount)Space O(coins.length · amount)

dp[i][a] is the number of combinations that make up amount a using only the first i coins. Row 0 (no coins available) can only make amount 0, in exactly one way (using none of them). For each coin, either skip it (dp[i-1][a]) or use at least one of it (dp[i][a - coins[i-1]], staying on row i since the coin can repeat).

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1
        for i in range(1, n + 1):
            for a in range(1, amount + 1):
                dp[i][a] = dp[i - 1][a]
                if a >= coins[i - 1]:
                    dp[i][a] += dp[i][a - coins[i - 1]]
        return dp[n][amount]

Filling the table for coins = [1, 2, 5], amount = 5 (the statement’s first example):

Watch the two amber sources of every new cell: the value directly above it (skip this coin) and the value to its left in the same row (use one more of it). The same-row read is what counts order-free combinations without double counting.

coins = [1, 2, 5]amount = 5dp[i][a]

none

Recurrence

dp[i][0] = 1 | dp[0][a>0] = 0

1 / 12

currentcomparingresult

Base cases: amount 0 has exactly one combination (use no coins) on every row, and with no coins available every positive amount has 0 ways.

Complexity: each of the (coins.length+1)·(amount+1) cells does O(1) work → O(coins.length · amount) time and space.

1-D Rolling Array

Time O(coins.length · amount)Space O(amount)

Row i only reads from row i-1 at the same column, and from row i itself at a smaller column. A single 1-D array, updated left-to-right for each coin, captures both: the “old” value at dp[a] before the update is dp[i-1][a], and the already-updated dp[a - coin] is the new dp[i][a - coin].

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]
        return dp[amount]

Same O(coins.length · amount) time, but space drops from a full table to a single row — O(amount) space.

Brute Force Recursion

2-D DP Table (Bottom-Up)

1-D Rolling Array

More 2-D DP practice