Pattern visualizer
Coin Change II
The insight: this counts COMBINATIONS, not permutations — [1,2,2] and [2,1,2] should count as the same way to make 5, not two different ways. Looping coins in the OUTER loop and amounts in the INNER loop enforces that: by fully processing one coin denomination before ever touching the next, a combination can only be built by adding coins in a fixed relative order, so the same multiset of coins can never be counted twice via two different orderings. dp[a] accumulates the running count of ways to make amount a using only the coin denominations introduced so far. Animated on: amount=5, coins=[1,2,5], count combinations (order doesn't matter).
Dynamic Programming
Initialize dp[0]=1, dp[1..5]=0, way to make sum 0: 1 empty combination
1FUNCTION coinChange2(amount, coins):2 dp = a table of size amount + 1, all set to 03 dp[0] = 14 FOR each coin in coins:5 FOR a from coin to amount:6 add dp[a-coin] to dp[a]7 RETURN dp[amount]
← / → step · space play · Home restart