Easy Problemscountingsubset

Coin change problem – Count Ways

Given coin denominations and a target sum, with an unlimited supply of each denomination, count the distinct combinations of coins that add up to the target. Two combinations that use the same coins in a different order are not counted separately.

Do this lesson first: coin change

Example input

coins = [1, 3, 4], amount = 5

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][s] = dp[i - 1][s] + dp[i][s - c_i], the second only when c_i <= s

Split the combinations that make s by whether they use the last allowed coin, c_i, at all. Those that use none of it are combinations of the first i - 1 coins making s: the cell above. Those that use at least one: take one c_i away and what is left is a combination making s - c_i in which c_i is STILL allowed, because there may be more of it. That is the cell c_i columns to the left in the same row. Every combination lands in exactly one of the two groups, so the cell is their sum. The flagship coin-change lesson splits on a different question, which coin was spent last. That split is right for the fewest coins, because the order coins are spent in does not change how many there are. For counting it is wrong: asking which coin came last counts 3 + 1 + 1, 1 + 3 + 1 and 1 + 1 + 3 as three answers. Deciding coin by coin whether it is used at all is what makes the order disappear.

Row 0 is the only base row. With no coins allowed, the only combination is the empty one, so dp[0][0] = 1 and every other cell in row 0 is 0. Column 0 computes, and is 1 all the way down for the same reason: taking no coins makes 0 whichever coins are allowed. Fill row by row and left to right within a row. The use-at-least-one case reads a cell to the LEFT in the SAME row, so that cell has to be final first, which a left-to-right sweep guarantees. Apart from adding where subset-sum takes the larger, that same-row read is what separates this table from subset-sum's, which reads the row above because each number there may be used only once.

Tabulation over (coins + 1) × (amount + 1) cells. Each cell reads the cell above and one cell to its left in its own row, so the grid collapses to one row of amount + 1 counts: for each coin in turn, sweep s upward and add ways[s - c] into ways[s]. With coins as the OUTER loop, that one-row version still counts combinations. Swap the two loops, amounts outside and coins inside, and nearly identical code counts ordered sequences instead: at amount 5 with these coins that is 6 rather than 3. The table on this page makes the coin loop a visible axis so that cannot happen by accident.

Time O(coins × amount)Space O(coins × amount), reducible to O(amount) with one row and coins as the outer loop

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is the only base row. With no coins allowed, the only combination is the empty one, so dp[0][0] = 1 and every other cell in row 0 is 0. Column 0 computes, and is 1 all the way down for the same reason: taking no coins makes 0 whichever coins are allowed. Fill row by row and left to right within a row. The use-at-least-one case reads a cell to the LEFT in the SAME row, so that cell has to be final first, which a left-to-right sweep guarantees. Apart from adding where subset-sum takes the larger, that same-row read is what separates this table from subset-sum's, which reads the row above because each number there may be used only once.

Rows ↓
Cols →

0

1

2

3

4

5

none

1

0

coin 1

1

coin 3

1

2

coin 4

1

2

3

Rows ↓row i: may use the first i coins

Cols →amount s: combinations that make s

coin-change-count-ways.ts

1function countWays(coins, amount) {
2 const n = coins.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0));
4 dp[0][0] = 1;
5 for (let i = 1; i <= n; i++) {
6 const c = coins[i - 1];
7 for (let s = 0; s <= amount; s++) {
8 dp[i][s] = dp[i - 1][s];
9 if (c <= s) dp[i][s] += dp[i][s - c];
10 }
11 }
12 return dp[n][amount];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

coin-change-count-ways.ts

1function countWays(coins, amount) {
2 const n = coins.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0));
4 dp[0][0] = 1;
5 for (let i = 1; i <= n; i++) {
6 const c = coins[i - 1];
7 for (let s = 0; s <= amount; s++) {
8 dp[i][s] = dp[i - 1][s];
9 if (c <= s) dp[i][s] += dp[i][s - c];
10 }
11 }
12 return dp[n][amount];
13}

Where people go wrong

Counting orders as different combinations. The natural first attempt carries the flagship lesson's one-row recurrence across with a sum in place of 1 + min and ways[0] = 1, ways[s] = the sum over coins c <= s of ways[s - c], and that counts sequences, not combinations. At amount 5 with coins {1, 3, 4} it gives 6, counting 3 + 1 + 1, 1 + 3 + 1 and 1 + 1 + 3 separately and 4 + 1 and 1 + 4 separately, where the answer is 3. The gap grows quickly: at amount 11 it is 104 against 9. Dividing out the duplicates afterwards has no clean formula. The fix is to decide one coin at a time, which is what the rows of this table do.

Count ordered sequences instead, so a 1 then a 3 differs from a 3 then a 1.
Drop the coin axis: one row over amounts, dp[s] = the sum over coins c <= s of dp[s - c]. That is climbing-stairs with the coins as step sizes. The second axis on this page exists to stop exactly that.
Allow each coin to be used at most once.
The use-it case reads the row above, dp[i - 1][s - c_i], instead of the current row. State and fill order stay; it is subset-sum with a count in place of a yes or no.
Ask for the fewest coins instead of the number of combinations.
That is coin-change-minimum-coins and the flagship lesson. A min replaces the sum and 1 + is added to the use-it case. Row 0 changes too: dp[0][0] = 0 coins, and every other amount is unreachable (infinity) rather than 0 ways. Because order does not change how many coins you used, the one-row recurrence becomes correct again and the coin axis can go.

Subset Sum Problem Coin Change – Minimum Coins to Make Sum