Coin Change Total Number of Ways in DSA C++

Mental Model

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

Analogy: Imagine you have different types of Lego blocks (coins) and you want to build a tower of a certain height (amount). You want to know in how many different ways you can stack these blocks to reach exactly that height.

Coins: [1, 2, 3]
Amount: 4

Ways to make 4:
1 -> 1 -> 1 -> 1
1 -> 1 -> 2
1 -> 3
2 -> 2

DP Table (rows: coins, cols: amounts):
   0 1 2 3 4
1: 1 1 1 1 1
2: 1 1 2 2 3
3: 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 dp array with dp[0] = 1 (one way to make amount 0)

dp = [1, 0, 0, 0, 0]

Why: We start with base case: one way to make amount zero (use no coins)

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

dp = [1, 1, 1, 1, 1]

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

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

dp = [1, 1, 2, 2, 3]

Why: Add ways using coin 2 to existing ways

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

dp = [1, 1, 2, 3, 4]

Why: Add ways using coin 3 to existing ways

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int coinChangeWays(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1; // base case: one way to make amount 0

    for (int coin : coins) {
        for (int x = coin; x <= amount; ++x) {
            dp[x] += dp[x - coin]; // add ways including current coin
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 3};
    int amount = 4;
    cout << coinChangeWays(coins, amount) << "\n";
    return 0;
}

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

initialize base case for dp

for (int coin : coins) {

iterate over each coin to build up ways

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

for each amount from coin value to target, update ways

dp[x] += dp[x - coin]; // add ways including current coin

add ways to make (x - coin) to ways to make x

Output

4

Complexity Analysis

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

Space: O(amount) because we use a one-dimensional dp array of size amount+1

vs Alternative: Compared to recursive solutions with overlapping subproblems, this dynamic programming approach avoids repeated calculations and is more efficient

Edge Cases

amount = 0

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

DSA C++

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

coins array empty

Returns 0 for any positive amount because no coins are available to make change

DSA C++

for (int coin : coins) {

coins contain duplicates

The code will overcount ways by treating each duplicate coin value as a separate denomination

DSA C++

for (int coin : coins) {

When to Use This Pattern

When asked to count the number of ways to make a sum with unlimited coins, use the coin change total number of ways pattern with dynamic programming to efficiently count combinations.

Common Mistakes

Mistake: Using a 2D dp array and double counting combinations by considering order
Fix: Use a 1D dp array and process coins in order to count combinations without order

Mistake: Initializing dp array with zeros but forgetting dp[0] = 1 base case
Fix: Always set dp[0] = 1 to represent one way to make amount zero

Summary

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

Use when you need the total number of combinations to form an amount with unlimited 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?
Given coins and a total amount, how many ways can you make that amount?

easy

A. The total number of ways to make the amount using given coins

B. The minimum number of coins needed to make the amount

C. The maximum coin value used to make the amount

D. The total sum of all coin values

Solution

1. Step 1: Understand the problem goal

   The problem asks for the count of different ways to combine coins to reach a target amount.

2. Step 2: Differentiate from similar problems

   This is not about minimum coins or maximum coin value, but total ways to form the amount.

3. Final Answer:

   The total number of ways to make the amount using given coins -> Option A

4. Quick Check:

   Count ways, not minimum or max coin [OK]

Hint: Count combinations, not minimum coins [OK]

Common Mistakes:

• Confusing total ways with minimum coins needed
• Thinking it's about maximum coin value
• Mixing sum of coins with number of ways

2. Which of the following is the correct way to initialize the DP array for the Coin Change Total Number of Ways problem in C++?

int amount = 5;
vector<int> dp(amount + 1, 0);
dp[0] = ?;

easy

A. 1

B. 0

C. -1

D. amount

Solution

1. Step 1: Understand base case initialization

   dp[0] represents ways to make amount 0, which is 1 (using no coins).

2. Step 2: Set dp[0] to 1

   Setting dp[0] = 1 allows building solutions for other amounts correctly.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   dp[0] = 1 means one way to make zero amount [OK]

Hint: dp[0] always 1 for coin change ways [OK]

Common Mistakes:

• Setting dp[0] to 0 causes no valid ways
• Using negative values for dp initialization
• Confusing dp array meaning with minimum coins

3. What is the output of the following C++ code?

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> coins = {1, 2};
    int amount = 3;
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int x = coin; x <= amount; x++) {
            dp[x] += dp[x - coin];
        }
    }
    cout << dp[amount] << endl;
    return 0;
}

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Trace dp array updates for coins {1, 2} and amount 3

   Initially dp = [1,0,0,0]. After coin=1: dp = [1,1,1,1]. After coin=2: dp[2]+=dp[0]=1+1=2, dp[3]+=dp[1]=1+1=2, so dp = [1,1,2,2].

2. Step 2: Final dp[3] value

   dp[3] = 2 means there are 2 ways to make amount 3 with coins 1 and 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

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

Hint: Add dp[x - coin] for each coin and amount [OK]

Common Mistakes:

• Mixing order of loops causing wrong counts
• Not initializing dp[0] to 1
• Confusing dp[x] update with subtraction

4. Find the error in this C++ code snippet for Coin Change Total Number of Ways:

vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int x = 1; x <= amount; x++) {
    for (int coin : coins) {
        if (coin <= x) {
            dp[x] += dp[x - coin];
        }
    }
}

medium

A. The dp array size is too small

B. dp[0] should be initialized to 0

C. The condition if (coin <= x) is incorrect

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

Solution

1. Step 1: Analyze loop order for correct counting

   Outer loop must be over coins to avoid counting duplicates; current code counts duplicates.

2. Step 2: Correct loop order

   Change outer loop to for (int coin : coins) and inner loop to for (int x = coin; x <= amount; x++) to count unique combinations.

3. Final Answer:

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

4. Quick Check:

   Loop order affects counting unique ways [OK]

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

Common Mistakes:

• Swapping loops causes counting duplicates
• Incorrect dp[0] initialization
• Wrong dp array size causing out-of-bounds

5. You have coins {1, 3, 5} and want to find the total number of ways to make amount 7. Which approach correctly computes this using dynamic programming?

hard

A. Sort coins descending and greedily subtract largest coin until amount is zero

B. Use a 2D dp array with rows as coins and columns as amounts, fill with minimum coins needed

C. Use a 1D dp array, initialize dp[0]=1, then for each coin, update dp[x] += dp[x - coin] for x from coin to amount

D. Use recursion without memoization to count ways

Solution

1. Step 1: Identify correct DP approach for total ways

   Using 1D dp array with dp[0]=1 and updating dp[x] for each coin counts total ways efficiently.

2. Step 2: Reject other approaches

   2D dp for minimum coins is different problem; greedy fails for total ways; recursion without memo is inefficient.

3. Final Answer:

   Use a 1D dp array, initialize dp[0]=1, then for each coin, update dp[x] += dp[x - coin] for x from coin to amount -> Option C

4. Quick Check:

   1D dp with coin loops counts ways correctly [OK]

Hint: 1D dp with coin loops counts ways, not min coins [OK]

Common Mistakes:

• Confusing total ways with minimum coins problem
• Using greedy which fails for counting ways
• Ignoring memoization causing slow recursion