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.

Analogy: Imagine you have different types of candies and want to fill a jar 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, 1 way to make 0 amount (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 (one way to make 0), others 0

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

Why: We know there is exactly one 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 to make (amount - 1) because coin 1 can be used.

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

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

Why: Add ways to make (amount - 2) to current ways, counting 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 to make (amount - 3) to current ways, counting combinations using coin 3.

Result:

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

Annotated Code

DSA C

#include <stdio.h>

int coinChangeWays(int coins[], int n, int amount) {
    int ways[amount + 1];
    for (int i = 0; i <= amount; i++) {
        ways[i] = 0;
    }
    ways[0] = 1; // base case: one way to make amount 0

    for (int i = 0; i < n; i++) {
        int coin = coins[i];
        for (int j = coin; j <= amount; j++) {
            ways[j] += ways[j - coin];
        }
    }
    return ways[amount];
}

int main() {
    int coins[] = {1, 2, 3};
    int amount = 4;
    int n = sizeof(coins) / sizeof(coins[0]);
    int totalWays = coinChangeWays(coins, n, amount);
    printf("Total ways to make %d = %d\n", amount, totalWays);
    return 0;
}

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

Initialize ways array with one way to make zero amount

for (int i = 0; i < n; i++) {

Iterate over each coin to update ways

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

For each amount from coin value to target, update ways

ways[j] += ways[j - coin];

Add ways to make (j - coin) to ways[j], counting new combinations

Output

Total ways to make 4 = 4

Complexity Analysis

Time: O(n * amount) because we update the ways array for each coin and each amount up to target

Space: O(amount) because we use a single array to store ways for all amounts up to target

vs Alternative: Compared to recursive solutions without memoization which can be exponential, this dynamic programming approach is efficient and avoids repeated calculations.

Edge Cases

amount = 0

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

DSA C

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

coins array empty

Returns 0 because no coins means no way to make positive amount

DSA C

for (int i = 0; i < n; i++) {

coins with duplicates

Duplicates do not affect correctness; ways are counted correctly

DSA C

for (int i = 0; i < n; i++) {

When to Use This Pattern

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

Common Mistakes

Mistake: Updating ways array in the wrong order causing counting permutations instead of combinations
Fix: Iterate coins outer loop and amounts inner loop forward to count combinations correctly

Summary

Counts how many different combinations of coins sum up to a target amount.

Use when you need the total number of ways to make a sum from given coin denominations.

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