Coin Change Total Number of Ways in DSA Java

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 the candies to reach that number.

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

Ways table (rows: coins, columns: amounts):
  amt: 0 1 2 3 4
coin1: 1 1 1 1 1
coin2: 1 1 2 2 3
coin3: 1 1 2 3 4

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: Initialize ways array with ways[0] = 1 (one way to make amount 0)

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

Why: We start knowing there is exactly one way to make amount zero: use no coins

Step 2: Use coin 1: update ways for amounts 1 to 4 by adding ways[amount - 1]

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

Why: With coin 1, each amount can be made by adding one coin 1 to previous amount

Step 3: Use coin 2: update ways for amounts 2 to 4 by adding ways[amount - 2]

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

Why: Coin 2 adds new combinations for amounts 2, 3, and 4

Step 4: Use coin 3: update ways for amounts 3 to 4 by adding ways[amount - 3]

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

Why: Coin 3 adds new combinations for amounts 3 and 4

Result:

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

Annotated Code

DSA Java

public class CoinChangeWays {
    public static int countWays(int[] coins, int amount) {
        int[] ways = new int[amount + 1];
        ways[0] = 1; // one way to make amount 0: no coins

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                ways[i] += ways[i - coin]; // add ways to make (i - coin) to ways[i]
            }
        }
        return ways[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 3};
        int amount = 4;
        int totalWays = countWays(coins, amount);
        System.out.println("Total ways to make amount " + amount + ": " + totalWays);
    }
}

ways[0] = 1; // one way to make amount 0: no coins

initialize base case: one way to make zero amount

for (int coin : coins) {

iterate over each coin to build up ways

for (int i = coin; i <= amount; i++) {

update ways for amounts from coin value up to target amount

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

add combinations that include current coin to ways[i]

Output

Total ways to make amount 4: 4

Complexity Analysis

Time: O(n * amount) because we iterate over each coin and for each coin over all amounts up to target

Space: O(amount) because we use a one-dimensional array to store ways for each amount

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

Edge Cases

amount is 0

returns 1 because there is exactly one way to make amount zero (no coins)

DSA Java

ways[0] = 1; // one way to make amount 0: no coins

coins array is empty

returns 0 because no coins means no way to make positive amounts

DSA Java

for (int coin : coins) {

amount less than smallest coin

returns 0 because no coin can be used to make the amount

DSA Java

for (int i = coin; i <= amount; i++) {

When to Use This Pattern

When asked to count the number of ways to make a total using given coin denominations, use the Coin Change Total Number of Ways pattern with dynamic programming to efficiently count combinations.

Common Mistakes

Mistake: Using a 2D array and double counting combinations by order
Fix: Use a 1D array and iterate coins first, then amounts, to count combinations without order duplicates

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

Summary

Counts how many different ways to make a target amount using given coin values.

Use when you need the total number of combinations to form an amount from coins.

The key is to build up ways incrementally by adding each coin's contribution to smaller amounts.

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 given amount using unlimited coins of given denominations

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

C. The maximum value of coins that can be used to make a given amount

D. The total number of coins available in the input array

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible ways to form a target amount using unlimited coins of given denominations.

2. Step 2: Differentiate from similar problems

   Unlike minimum coins problem, here we count ways, not minimize coins.

3. Final Answer:

   The total number of ways to make a given amount using unlimited coins of given denominations -> Option A

4. Quick Check:

   Count ways, not minimum coins [OK]

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

Common Mistakes:

• Confusing with minimum coins problem
• Thinking about maximum coin value
• Counting coins instead of ways

2. Which of the following Java code snippets correctly initializes the DP array for the Coin Change Total Number of Ways problem for amount 5?

easy

A. int[] dp = new int[6]; dp[0] = 1;

B. int[] dp = new int[5]; dp[0] = 1;

C. int[] dp = new int[6]; dp[1] = 1;

D. int[] dp = new int[5]; dp[1] = 1;

Solution

1. Step 1: Determine DP array size

   For amount 5, dp array size should be 6 to include index 0 to 5.

2. Step 2: Initialize base case

   dp[0] = 1 means one way to make amount 0 (using no coins).

3. Final Answer:

   int[] dp = new int[6]; dp[0] = 1; -> Option A

4. Quick Check:

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

Hint: DP array size = amount + 1; dp[0] = 1 base case [OK]

Common Mistakes:

• Using dp array size equal to amount instead of amount+1
• Initializing dp[1] instead of dp[0]
• Forgetting to set base case dp[0] = 1

3. What is the output of the following Java code snippet?

int[] coins = {1, 2};
int amount = 3;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
  for (int i = coin; i <= amount; i++) {
    dp[i] += dp[i - coin];
  }
}
System.out.println(dp[amount]);

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0] initially, dp[0] = 1.

2. Step 2: Process coin 1

   For i=1 to 3: dp[1]+=dp[0]=1, dp[2]+=dp[1]=1, dp[3]+=dp[2]=1; dp = [1,1,1,1]

3. Step 3: Process coin 2

   For i=2 to 3: dp[2]+=dp[0]=1+1=2, dp[3]+=dp[1]=1+1=2; dp = [1,1,2,2]

4. Step 4: Final dp[3]

   dp[3] = 2 means 2 ways: {1+1+1, 1+2}

5. Final Answer:

   2 -> Option C

6. Quick Check:

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

Hint: Add ways for each coin from coin to amount [OK]

Common Mistakes:

• Not updating dp correctly inside nested loops
• Confusing dp[i] with dp[i-1]
• Miscounting combinations

4. Identify the error in the following Java code for Coin Change Total Number of Ways:

int[] coins = {1, 2, 3};
int amount = 4;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 1; i <= amount; i++) {
  for (int coin : coins) {
    if (i >= coin) {
      dp[i] += dp[i - coin];
    }
  }
}
System.out.println(dp[amount]);

medium

A. The dp array size is too small

B. dp[0] should be initialized to 0

C. The condition i >= coin is incorrect

D. The outer loop should iterate over coins, inner over amounts

Solution

1. Step 1: Analyze loop order

   Outer loop iterates over amounts, inner over coins, which counts permutations, not combinations.

2. Step 2: Correct loop order

   Outer loop should iterate over coins, inner over amounts to count combinations correctly.

3. Final Answer:

   The outer loop should iterate over coins, inner over amounts -> Option D

4. Quick Check:

   Loop order affects counting ways [OK]

Hint: Outer loop coins, inner loop amounts for combinations [OK]

Common Mistakes:

• Swapping loop order causing wrong counts
• Incorrect dp initialization
• Misusing conditions inside loops

5. Given coins = {1, 3, 5} and amount = 7, how many total ways are there to make amount 7 using unlimited coins? Use the Coin Change Total Number of Ways approach.

hard

A. 5

B. 4

C. 6

D. 7

Solution

1. Step 1: Initialize dp array

   dp size = 8, dp[0] = 1, others 0.

2. Step 2: Process coin 1

   Update dp for i=1 to 7: dp[i] += dp[i-1], dp = [1,1,1,1,1,1,1,1]

3. Step 3: Process coin 3

   For i=3 to 7: dp[3]+=dp[0]=2, dp[4]+=dp[1]=2, dp[5]+=dp[2]=2, dp[6]+=dp[3]=3, dp[7]+=dp[4]=3; dp = [1,1,1,2,2,2,3,3]

4. Step 4: Process coin 5

   For i=5 to 7: dp[5]+=dp[0]=3, dp[6]+=dp[1]=4, dp[7]+=dp[2]=4; dp = [1,1,1,2,2,3,4,4]

5. Final Answer:

   4 -> Option B

6. Quick Check:

   Count ways with coins 1,3,5 for amount 7 = 4 [OK]

Hint: Add ways coin by coin updating dp array [OK]

Common Mistakes:

• Miscounting dp updates for each coin
• Forgetting base case dp[0] = 1
• Mixing permutations with combinations