Coin Change Problem (Number of Ways)

Given an integer value n representing the target amount of cents, and an array of coin denominations S = [S_0, S_1, ..., S_m-1]. Find the number of unique combinations to make change for n cents, assuming an infinite supply of each coin denomination.

Examples

Example 1

Target Value (n): 4
Coin Denominations (S): [1, 2, 3]
Combinations:
1. {1, 1, 1, 1}
2. {1, 1, 2}
3. {2, 2}
4. {1, 3}
Output: 4

Example 2

Target Value (n): 10
Coin Denominations (S): [2, 5, 3, 6]
Output: 5

Mathematical Substructure

Let count(S, m, n) be the function to find the number of ways to make change for n using the first m coins:

Exclude the m-th coin: Solve the problem for n cents with m - 1 coins.
Include the m-th coin: Solve the problem for n - S[m - 1] cents with all m coins.

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m-1])

Base Cases

If n === 0, return 1 (1 way: choosing no coins).
If n < 0, return 0 (no way to make negative change).
If m === 0 && n > 0, return 0 (no coins available to make change).

1. Naive Recursive Solution

function countWaysRecursive(S, m, n) {
    // If n is 0 then there is 1 solution (do not include any coin)
    if (n === 0) return 1;
 
    // If n is less than 0 then no solution exists
    if (n < 0) return 0;
 
    // If there are no coins and n is greater than 0, then no solution exists
    if (m <= 0 && n > 0) return 0;
 
    // Sum of solutions:
    // (a) excluding the last coin
    // (b) including at least one of the last coin
    return countWaysRecursive(S, m - 1, n) + countWaysRecursive(S, m, n - S[m - 1]);
}

2. Memoization Solution (Top-Down DP)

function countWaysMemoization(S, m, n) {
    // Initialize 2D memo table with -1
    const memo = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
 
    function helper(i, j) {
        if (j === 0) return 1;
        if (j < 0) return 0;
        if (i <= 0) return 0;
 
        if (memo[i][j] !== -1) return memo[i][j];
 
        memo[i][j] = helper(i - 1, j) + helper(i, j - S[i - 1]);
        return memo[i][j];
    }
 
    return helper(m, n);
}

3. Tabulation Solution (Bottom-Up DP)

We build a 2D table dp of size (m+1) x (n+1).

function countWaysTabulation(S, m, n) {
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
    // Base case: 1 way to make change for 0 cents
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
 
    // Fill table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // Exclude coin i-1
            let exclude = dp[i - 1][j];
            
            // Include coin i-1 if it doesn't exceed target value j
            let include = (j - S[i - 1] >= 0) ? dp[i][j - S[i - 1]] : 0;
 
            dp[i][j] = exclude + include;
        }
    }
 
    return dp[m][n];
}

4. Space Optimized Tabulation (1D DP Array)

Notice that to compute dp[i][j], we only need values from the same column of the previous row (dp[i-1][j]) and a previous column of the current row (dp[i][j - S[i-1]]). Therefore, we can reduce the space complexity to O(n) using a 1D array.

function countWaysSpaceOptimized(S, n) {
    // dp[i] will store the number of solutions for value i
    const dp = new Array(n + 1).fill(0);
 
    // Base case (1 way to make 0 change)
    dp[0] = 1;
 
    // Pick all coins one by one and update the dp[] values
    // after the index greater than or equal to the value of the picked coin
    for (let coin of S) {
        for (let j = coin; j <= n; j++) {
            dp[j] += dp[j - coin];
        }
    }
 
    return dp[n];
}
 
// Driver code
const S = [1, 2, 3];
const n = 4;
console.log("Number of ways to make change:", countWaysSpaceOptimized(S, n));
// Output: Number of ways to make change: 4

Complexity Analysis

Time Complexity: O(M * N)
- Where M is the number of coin denominations and N is the target value.
Space Complexity:
- O(M * N) for standard 2D Tabulation/Memoization.
- O(N) for the Space-Optimized 1D array approach.

Longest Common Subsequence Edit Distance Problem