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.