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.
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
Edge cases
dp[0]=1 — the empty combination.
dp[amount] stays 0.
Inner range is empty — coin contributes nothing.