Coin Change Total Number of Ways in DSA Typescript

Mental Model

We want to find how many different ways we can make a total amount using given coin values, counting all combinations.

Analogy: Imagine you have different types of candies and want to fill a bag with a certain number of candies. You count all the ways to combine candies to reach that number.

coins: [1, 2, 3]
amount: 4

ways array (index = amount):
[1, 0, 0, 0, 0]
↑
Initially, ways[0] = 1 means there is 1 way to make amount 0 (use no coins).

Dry Run Walkthrough

Input: coins: [1, 2, 3], amount: 4

Goal: Find total number of ways to make amount 4 using coins 1, 2, and 3.

Step 1: Start with ways array: ways[0]=1, others 0

ways: [1, 0, 0, 0, 0]

Why: We know there is exactly 1 way to make amount 0: use no coins.

Step 2: Use coin 1: update ways for amounts 1 to 4

ways: [1, 1, 1, 1, 1]

Why: For each amount, add ways[amount - 1] because coin 1 can make all amounts by adding one coin repeatedly.

Step 3: Use coin 2: update ways for amounts 2 to 4

ways: [1, 1, 2, 2, 3]

Why: Add ways[amount - 2] to current ways to include combinations using coin 2.

Step 4: Use coin 3: update ways for amounts 3 to 4

ways: [1, 1, 2, 3, 4]

Why: Add ways[amount - 3] to include combinations using coin 3.

Result:

ways: [1, 1, 2, 3, 4]
Total ways to make amount 4 = 4

Annotated Code

DSA Typescript

class CoinChange {
  static totalWays(coins: number[], amount: number): number {
    const ways = new Array(amount + 1).fill(0);
    ways[0] = 1; // base case: 1 way to make amount 0

    for (const coin of coins) {
      for (let a = coin; a <= amount; a++) {
        ways[a] += ways[a - coin]; // add ways to make (a - coin) to ways[a]
      }
    }

    return ways[amount];
  }
}

// Driver code
const coins = [1, 2, 3];
const amount = 4;
const result = CoinChange.totalWays(coins, amount);
console.log(`Total ways to make amount ${amount} = ${result}`);

ways[0] = 1; // base case: 1 way to make amount 0

Initialize ways array with 1 way to make amount 0 (no coins).

for (const coin of coins) {

Iterate over each coin to build up ways to make amounts.

for (let a = coin; a <= amount; a++) {

For each amount from coin value up to target, update ways.

ways[a] += ways[a - coin]; // add ways to make (a - coin) to ways[a]

Add ways to make (a - coin) because adding current coin forms new combinations.

return ways[amount];

Return total ways to make the target amount.

Output

Total ways to make amount 4 = 4

Complexity Analysis

Time: O(n * amount) because we loop through each coin and for each coin, we loop through amounts up to the target.

Space: O(amount) because we use an array of size amount+1 to store ways counts.

vs Alternative: Compared to recursive solutions without memoization, this dynamic programming approach avoids repeated calculations and runs much faster.

Edge Cases

amount = 0

Returns 1 because there is exactly one way to make amount 0 (use no coins).

DSA Typescript

ways[0] = 1; // base case: 1 way to make amount 0

coins array empty

Returns 0 for any amount > 0 because no coins are available to make the amount.

DSA Typescript

for (const coin of coins) { ... } // loop skipped if coins empty

coins with duplicates

Duplicates do not affect correctness; combinations count includes all ways using all coins.

DSA Typescript

for (const coin of coins) { ... } // processes each coin independently

When to Use This Pattern

When asked to count the number of ways to make a total using given coin values, use the Coin Change Total Number of Ways pattern with dynamic programming to build solutions from smaller amounts.

Common Mistakes

Mistake: Using nested loops in wrong order causing counting permutations instead of combinations.
Fix: Loop over coins first, then amounts, to count combinations without duplicates.

Mistake: Not initializing ways[0] = 1, leading to zero ways for all amounts.
Fix: Set ways[0] = 1 to represent the base case of making amount zero.

Summary

Calculates how many different combinations of coins can make a target amount.

Use when you need to count all possible ways to form an amount from given coin denominations.

The key is to build up the number of ways for each amount by adding ways from smaller amounts using each coin.

Practice

1. What does the "Coin Change Total Number of Ways" problem ask you to find?

easy

A. The total number of ways to make a target amount using given coin denominations.

B. The minimum number of coins needed to make a target amount.

C. The maximum value of coins that can be used to reach the target.

D. The total sum of all coin denominations.

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible ways to make a target amount using given coins.

2. Step 2: Differentiate from similar problems

   Unlike minimum coins problem, this counts combinations, not minimum count.

3. Final Answer:

   The total number of ways to make a target amount using given coin denominations. -> Option A

4. Quick Check:

   Counting ways = total combinations [OK]

Hint: Count combinations, not minimum coins needed [OK]

Common Mistakes:

• Confusing with minimum coin count problem
• Thinking about maximum coin value instead of ways
• Ignoring repeated use of coins

2. Which of the following TypeScript code snippets correctly initializes the DP array for the coin change ways problem for amount 5?

easy

A. const dp = new Array(5).fill(1);

B. const dp = new Array(6).fill(0); dp[0] = 1;

C. const dp = new Array(5).fill(0); dp[1] = 1;

D. const dp = new Array(6).fill(1); dp[0] = 0;

Solution

1. Step 1: Understand DP array size and initialization

   For amount 5, dp array size should be 6 (0 to 5). dp[0] = 1 means one way to make amount 0.

2. Step 2: Check each option

   const dp = new Array(6).fill(0); dp[0] = 1; correctly creates dp of size 6, fills 0, sets dp[0]=1. Others have wrong size or initialization.

3. Final Answer:

   const dp = new Array(6).fill(0); dp[0] = 1; -> Option B

4. Quick Check:

   dp size = amount+1, dp[0] = 1 [OK]

Hint: DP array size = amount + 1, dp[0] = 1 [OK]

Common Mistakes:

• Using dp array size equal to amount instead of amount+1
• Not setting dp[0] = 1
• Filling dp with 1 instead of 0 initially

3. What is the output of the following TypeScript code?

const coins = [1, 2];
const amount = 3;
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
  for (let x = coin; x <= amount; x++) {
    dp[x] += dp[x - coin];
  }
}
console.log(dp[amount]);

medium

A. 3

B. 0

C. 1

D. 2

Solution

1. Step 1: Trace dp updates for coin 1

   dp after coin 1: dp[1]=1, dp[2]=1, dp[3]=1 (only using coin 1)

2. Step 2: Trace dp updates for coin 2

   dp[2]+=dp[0]=1+1=2, dp[3]+=dp[1]=1+1=2; final dp = [1,1,2,2]

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Ways to make 3 with [1,2] = 2 [OK]

Hint: Add ways from smaller amounts using each coin [OK]

Common Mistakes:

• Not updating dp correctly inside nested loops
• Confusing dp[x] with dp[x - coin]
• Missing dp[0] = 1 initialization

4. Find the error in this TypeScript code for coin change ways and select the fix:

const coins = [1, 2, 3];
const amount = 4;
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let i = 0; i <= coins.length; i++) {
  for (let x = coins[i]; x <= amount; x++) {
    dp[x] += dp[x - coins[i]];
  }
}
console.log(dp[amount]);

medium

A. Use for (const coin of coins) instead of index loop

B. Initialize dp array with 1 instead of 0

C. Change loop to for (let i = 0; i < coins.length; i++)

D. Set dp[amount] = 0 before loops

Solution

1. Step 1: Identify loop index error

   The loop runs i from 0 to coins.length inclusive, causing out-of-bounds access at coins[coins.length].

2. Step 2: Fix loop condition

   Change to i < coins.length to avoid accessing undefined coin.

3. Final Answer:

   Change loop to for (let i = 0; i < coins.length; i++) -> Option C

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use < length, not <= length for array loops [OK]

Common Mistakes:

• Using <= in for loop causing out-of-bounds error
• Not initializing dp[0] = 1
• Confusing index and value in loops

5. Given coins = [1, 3, 5] and amount = 7, how many total ways are there to make amount 7 using any number of these coins?

hard

A. 4

B. 8

C. 7

D. 6

Solution

1. Step 1: Initialize dp array and process coin 1

   dp size 8, dp[0]=1. Using coin 1, dp[x]=1 for x=1 to 7.

2. Step 2: Update dp with coin 3

   For x=3 to 7, dp[x]+=dp[x-3]: dp[3]=2, dp[4]=1+dp[1]=2, dp[5]=1+dp[2]=2, dp[6]=1+dp[3]=3, dp[7]=1+dp[4]=3.

3. Step 3: Update dp with coin 5

   For x=5 to 7, dp[5]+=dp[0]=2+1=3, dp[6]+=dp[1]=3+1=4, dp[7]+=dp[2]=3+1=4.

4. Step 4: Final dp array and answer

   Final dp[7] = 4 ways. The combinations are: 7x1, 4x1+1x3, 1x1+2x3, 2x1+1x5.

5. Final Answer:

   4 -> Option A

6. Quick Check:

   Count all combinations with coins [1,3,5] for 7 = 4 [OK]

Hint: Build dp adding ways coin by coin [OK]

Common Mistakes:

• Missing some combinations with multiple coins
• Confusing permutations with combinations
• Incorrect dp updates order