—
coin
Given coin denominations and a target amount, count the number of distinct combinations that sum to it. The key trick is an outer loop over coins and an inner loop over amounts — this naturally prevents double-counting permutations of the same combination.
Given coins = [1, 2, 5] and amount = 5, return the number of distinct coin combinations that sum to 5. Answer: 4 — those combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1. Note that 2+1+1+1 and 1+2+1+1 count as the same combination — order does not matter.
dp[a] = number of ways to make amount a. The recurrence is dp[a] += dp[a - coin] with dp[0] = 1. The crucial detail is loop order: put coins in the outer loop and amounts in the inner loop. This means each coin is fully committed before moving on, so every counted path uses coins in a fixed order — combinations only, no permutations.dp[0] = 1 — there is exactly one way to make amount zero: use no coins at all. Every other cell starts at 0.a, add dp[a - coin] — the ways already counted that can be extended by one more of this coin. Starting at a = coin avoids negative indexing.dp[amount] is the total number of combinations. It is always ≥ 0; the problem guarantees an answer exists (0 is valid when no combination reaches the target).coins = [1, 2], amount = 3, the coins-outer order gives 2 (combinations: 1+2, 1+1+1) while amounts-outer gives 3 (also counting 2+1 as distinct from 1+2).k = number of coin denominations. The 1-D rolling table uses O(amount) space — the same as Coin Change I. Top-down memoized DFS reaches the same asymptotic cost but requires careful handling of the combination-vs-permutation distinction via the starting-coin index.
dp[0..5] to 0; set dp[0] = 1 (one way to make 0: use no coins).1function change(amount: number, coins: number[]): number {2▶ const dp: number[] = new Array(amount + 1).fill(0);3▶ dp[0] = 1; // one way to make amount 0: use no coins45 for (const coin of coins) { // outer: iterate coins6 for (let a = coin; a <= amount; a++) { // inner: amounts forward7 dp[a] += dp[a - coin]; // add ways that include this coin8 }9 }1011 return dp[amount];12}
function change(amount: number, coins: number[]): number {
const dp: number[] = new Array(amount + 1).fill(0);
dp[0] = 1; // one way to make amount 0: use no coins
for (const coin of coins) { // outer: iterate coins
for (let a = coin; a <= amount; a++) { // inner: amounts forward
dp[a] += dp[a - coin]; // add ways that include this coin
}
}
return dp[amount];
}amount + 1 filled with 0represents “no ways found yet.” dp[0] = 1 is the only hard-coded base case: there is exactly one way to form amount zero — use nothing.c, it can only appear as an earlier “layer”, so no permutation of the same multiset is ever counted twice.a = coin (not 0) avoids negative indices. Running forward is what makes coins unbounded — when we compute dp[a], dp[a - coin] has already been updated in this same coin pass, so the same denomination can contribute multiple times.dp[a] += dp[a - coin]reads: “every way to build amount a - coin becomes a new way to build aby appending one more of this coin.” The sum across all coins at all amounts gives the total combination count.dp[amount]is the final answer. Unlike Coin Change I, there is no “-1 sentinel” — if no combination reaches the target, the cell simply stays 0.k coins iterates through all amount cells once. O(amount) space for the 1-D table. No recursion overhead.dp[a] += dp[a - coin] for every coin at every amount.a from amount down to coin) so each denomination is only “spent” once.coinIndex parameter to fix the coin order and avoid permutation double-counting. Same O(amount × k) time but with call-stack overhead.amount = 0 returns 1 (the empty combination). A single coin equal to amount gives 1. No coin divides amount gives 0.function change(amount: number, coins: number[]): number {
const dp: number[] = new Array(amount + 1).fill(0);
dp[0] = 1; // one way to make amount 0: use no coins
for (const coin of coins) { // outer: iterate coins
for (let a = coin; a <= amount; a++) { // inner: amounts forward
dp[a] += dp[a - coin]; // add ways that include this coin
}
}
return dp[amount];
}k coins iterates through all amount cells once. O(amount) space for the 1-D table. No recursion overhead.Explore the decision tree directly: at each coin you may either skip it (move to the next coin) or take it (stay on the same coin, subtracting its value). Sum the leaf counts where remaining === 0. Fixing the coin order avoids counting a combination more than once.
function change(amount: number, coins: number[]): number {
function count(i: number, remaining: number): number {
if (remaining === 0) return 1; // exact combination found
if (remaining < 0 || i === coins.length) return 0;
// Skip coin i, OR take coin i (and may take it again).
return count(i + 1, remaining)
+ count(i, remaining - coins[i]);
}
return count(0, amount);
}(i, remaining) states are recomputed across countless branches, blowing up exponentially. Cache results by (i, remaining)— or collapse to the 1-D rolling array above — for the O(amount · coins) optimal.| "count the number of combinations/ways to reach a target" | coins outer, amounts forward, dp[a] += dp[a-coin], dp[0]=1 |
| denominations unlimited, order does NOT matter | coins-outer DP — fixes ordering, prevents permutation double-count |
| "count distinct orderings / sequences" | amounts outer, coins inner (Combination Sum IV pattern) |
| counting ways vs minimizing count | swap Math.min(…+1) → +=, swap Infinity seed → 0, swap dp[0]=0 → dp[0]=1 |
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];coins = [1, 2, 5], amount = 5, what is the answer?coins = [2], amount = 3. What does the function return?coin = 1 (the first coin) with coins = [1, 2, 5], amount = 5, what is dp[3]?