Coin Change II · DSA Prep

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))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], amount = 4 (a small illustrative case):

1 / 7

comparingseenresult

Base case: with amount 0, there is exactly one way to make it (use no coins) regardless of how many coin types are available.

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.