Coin Change II
Count the number of combinations of coins (unlimited supply) that make amount. Order doesn't matter.
Intuition
The trap is counting 1+2 and 2+1 as different. The fix is loop order: process coins in the outer loop. Then dp[a] only ever counts ways that use coins in one fixed order, so each combination is counted exactly once. dp[a] += dp[a-coin] means: every way to make a−coin extends to a way to make a using this coin.
Counting combinations, not permutations — and the loop order is what enforces that. Putting the coin loop outside means each coin is fully considered before the next one exists, so [1,2] and [2,1] can never both be produced. This one detail separates coin-change-II from combination-sum-IV, which is the same recurrence with the loops swapped.
Approach
Unbounded knapsack counting
dp[0]=1 (one way to make zero: no coins). For each coin, for a from coin..amount: dp[a] += dp[a-coin]. Left-to-right inner loop lets the same coin be reused.
Why coin-outer kills permutations
After finishing coin c, dp counts combinations using only the coins seen so far, in a canonical order. Swapping the loops (amount outer) would count 1+2 and 2+1 separately — that's Combination Sum IV, a different problem.
1-D is enough
The 2-D table dp[coin_idx][a] collapses to one row because each row only reads itself (reuse) and the previous row (skip coin).
Solution & live demo
Common pitfalls
Putting the amount loop outside
for a in range(1, amount + 1):
for coin in coins:
if coin <= a: dp[a] += dp[a - coin]for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]With the amount outside, every coin is available at every step, so 1+2 and 2+1 are counted as two different ways — that's the permutation count. Coin-outside fixes an order on the coins, which is exactly what makes a combination unordered.
Initialising dp[0] to zero
dp = [0] * (amount + 1)
dp = [0] * (amount + 1) dp[0] = 1
There is exactly one way to make amount 0 — take nothing. That 1 is the seed every count multiplies up from; leaving it at 0 makes the whole table zero.
Iterating the inner loop downward
for a in range(amount, coin - 1, -1):
for a in range(coin, amount + 1):
Descending is the 0/1-knapsack order, which uses each coin at most once. Coins here are unlimited, so dp[a - coin] must already include this coin's own contributions — that requires ascending order.
Edge cases
dp[0]=1 — the empty combination.
dp[amount] stays 0.
Inner range is empty — coin contributes nothing.