Coin Change II
Problem
Given coins of distinct denominations and an integer amount, return the number of combinations that make up amount. You may use each coin an unlimited number of times.
amount = 5, coins = [1, 2, 5]4def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for x in range(c, amount + 1):
dp[x] += dp[x - c]
return dp[amount]function change(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins) {
for (let x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return dp[amount];
}class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int c : coins) {
for (int x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return dp[amount];
}
}int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins) {
for (int x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return dp[amount];
}Explanation
We want to count combinations (not permutations) that add up to amount, using each coin as many times as we like. The neat trick is the order of the two loops: looping coins on the outside avoids counting 1+2 and 2+1 as different.
The array dp[x] holds the number of ways to make amount x using the coins considered so far. We seed it with dp[0] = 1, because there is exactly one way to make 0: pick no coins.
For each coin c, we sweep x from c up to amount and do dp[x] += dp[x - c]. This says: every way to build x - c can be extended by adding one more coin c to reach x.
Because each coin is fully processed before moving to the next, every combination is generated in a fixed coin order, so no duplicates are counted.
Example: amount = 5, coins = [1, 2, 5]. After processing all coins, dp[5] = 4, matching the four combinations 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1.