Problem Statement
Coin Change II
You have a list of coin values, like [1, 2, 5], and a target amount, like 5. You can use each coin as many times as you want. The question is: how many different ways can you add coins up to exactly the target? Here, [1, 2, 2] and [2, 2, 1] count as the SAME way, because they use the same coins. We only care about which coins and how many of each, not the order. If the amount cannot be made at all, the answer is 0. The tool for this is a running tally. We keep a small table where each slot stores "how many ways can I make this amount so far," and we fill it in one coin at a time. Adding coins one type at a time is the trick that stops us from counting the same group twice.
Signals to notice
Brute force first
Recursively try all combinations — exponential without memoization. Many subproblems are re-solved. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DP: dp[j] = number of ways to make amount j. For each coin, update dp left-to-right: dp[j] += dp[j - coin]. Process coins in the outer loop to avoid counting different orderings. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on amount=5, coins=[1,2,5]
init: dp=[1,0,0,0,0,0] (dp[0]=1, base case) coin=1, sweep a=1..5: each dp[a]+=dp[a-1] -> dp=[1,1,1,1,1,1] (only 1s) coin=2, a=2: dp[2]+=dp[0]=2; a=3: dp[3]+=dp[1]=2; a=4: dp[4]+=dp[2]=3; a=5: dp[5]+=dp[3]=3 -> dp=[1,1,2,2,3,3] coin=5, a=5: dp[5]+=dp[0] -> dp[5]=4 -> dp=[1,1,2,2,3,4] return dp[5] = 4 (5; 2+2+1; 2+1+1+1; 1+1+1+1+1)
What must stay true
By processing one coin at a time (outer loop), each combination is counted exactly once in sorted coin order. If coins were in the inner loop, [1,2] and [2,1] would be counted separately. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
dp = array of zeros, size amount+1
dp[0] = 1 // one way to make 0: pick nothing
for coin in coins: // coins OUTER -> counts combinations
for a = coin .. amount: // left-to-right (unbounded use)
dp[a] += dp[a - coin]
return dp[amount]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Swapping the loop order — coins must be the outer loop. If amount is the outer loop and coins are inner, you count permutations (order matters) instead of combinations (order doesn't). When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.