Coin Change II

Signal

"Count the combinations" (order doesn't matter) rather than "count the sequences" (order matters) is a tell that one dimension of your DP must be "which coins have I considered so far," not just "how much amount is left" — otherwise you double-count the same multiset of coins in different orders.

Approach

Think of it as a 2-D table dp[i][a] = number of ways to make amount a using only the first i coin types. For each coin, you either use zero of it (inherit dp[i-1][a]) or use one more of it (dp[i][a - coin], staying on row i since the same coin can be reused). Processing one coin fully across all amounts before moving to the next coin is what enforces "combinations, not permutations" — the loop order is the algorithm here.

Skeleton

dp = [0] * (amount + 1); dp[0] = 1
for coin in coins:              # outer: one coin type at a time
    for a in range(coin, amount + 1):   # inner: amounts, ascending
        dp[a] += dp[a - coin]
return dp[amount]

Solution

def change(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]

Complexity

O(amount · len(coins)) time — each coin scans the full amount range once. O(amount) space for the 1-D table (the "which coins so far" dimension collapses because each coin is only ever added once, in order).

Pitfalls

• Swapping the loop order (amounts outer, coins inner) silently changes the problem to counting sequences — the classic bug, and it inflates the answer by counting [1,2] and [2,1] as different ways to make 3.
• This looks identical in shape to the 0/1 knapsack and unbounded-knapsack "count ways" problems — the outer-coin/inner-amount order is what makes it unbounded (each coin can be reused within its own pass) rather than 0/1.
• dp[0] = 1 (one way to make zero: use no coins) is the base case that makes the rest of the recurrence work — easy to forget and get an all-zero table.