Coin Change - Minimum Coins to Make Sum: Backtracking and Dynamic Programming

In this blog post, we will tackle the Minimum Coin Change problem, a classic dynamic programming challenge. The goal of this problem is to determine the minimum number of coins required to make a given amount using a specified set of coin denominations. First, we will explore the backtracking (recursive) solution, followed by an optimized approach using dynamic programming. A Mermaid diagram will be used to represent the state transitions for better clarity.

---

Problem Statement

Given a set of coins coins[] of distinct denominations and an integer amount, the task is to determine the fewest number of coins needed to make up the amount. If that amount of money cannot be made up by any combination of the coins, return -1.

For example:

coins = [1, 2, 5], amount = 11
Output: 3 (11 = 5 + 5 + 1)` 

---

Part 1: Backtracking Approach

Explanation

The backtracking approach tries to explore all possible combinations of coins by making recursive choices at each step. At each recursive call, we have two options:

1. Pick the current coin and subtract its value from the amount.
2. Skip the current coin and move to the next one.

This process continues until:

• We find a valid solution where the remaining amount is 0 (base case).
• We hit an invalid state where the amount becomes negative.

The recursive tree grows exponentially, exploring every possible path to form the amount, leading to inefficiency. Below is the pseudocode for the backtracking approach:

Backtracking Code (JavaScript)

function minCoinsBacktracking(coins, amount) {
    function backtrack(remaining, coinCount) {
        // Base case: If remaining amount is zero, we've found a valid solution
        if (remaining === 0) return coinCount;
        if (remaining < 0) return Infinity;  // Invalid state, not a solution

        let minCoins = Infinity;

        // Try each coin and recurse
        for (let coin of coins) {
            const result = backtrack(remaining - coin, coinCount + 1);
            minCoins = Math.min(minCoins, result);
        }

        return minCoins;
    }

    const result = backtrack(amount, 0);
    return result === Infinity ? -1 : result;
}

Time Complexity:

This approach has an exponential time complexity O(nm)O(n^m)O(nm), where nnn is the amount and mmm is the number of coins. It explores all combinations, leading to a slow performance.

State Diagram (Mermaid)

Here’s a diagram representing the state transitions for the backtracking process:

This diagram highlights how each node represents a state (remaining amount), and each edge represents using a coin denomination. The tree expands exponentially as it explores each possible combination.

---

Part 2: Optimizing with Dynamic Programming

Dynamic Programming Approach

The backtracking approach is inefficient due to overlapping subproblems—states where we attempt to make the same remaining amount multiple times. To eliminate this redundancy, we can use dynamic programming (DP). The idea is to build a DP table (dp[]) where each entry dp[i] stores the minimum number of coins needed to make the amount i.

1. Initialization:

   • Set dp[0] = 0 because 0 coins are needed to make amount 0.
   • For all other entries, initialize dp[i] to infinity, meaning that amount cannot initially be formed.

2. DP Transition:

   • For each coin, update the DP table for amounts greater than or equal to the coin’s value.
   • The recurrence relation is: dp[i]=min⁡(dp[i],dp[i−coin]+1)dp[i] = \min(dp[i], dp[i - \text{coin}] + 1)dp[i]=min(dp[i],dp[i−coin]+1)
   • This means that for amount i, we can either keep the current number of coins (dp[i]) or try using the current coin and see if it reduces the number of coins (dp[i - coin] + 1).

Dynamic Programming Code (JavaScript)

function minCoinsDP(coins, amount) {
    // Initialize dp array with Infinity, and set dp[0] to 0
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    // For each coin, update the dp table
    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

Time Complexity:

• Time Complexity: $O(n×m)O(n \times m)O(n×m)$, where nnn is the target amount and mmm is the number of coins.
• Space Complexity: $O(n)O(n)O(n)$ due to the DP table.

State Diagram

Now, let’s visualize how the dynamic programming table is filled using a diagram

In this diagram, each node represents a value of dp[i], which stores the minimum number of coins required to make up the amount i. As the algorithm processes each coin, it updates the DP table by minimizing the coin count for each amount.

For example:

• dp[5] is updated to 1 when using the 5-coin.
• dp[10] becomes 2 (since we can use two 5-coins), and dp[11] becomes 3 (two 5-coins and one 1-coin).

---

Part 3: Comparison of Approaches

Approach	Time Complexity	Space Complexity	Pros	Cons
Backtracking	(O(n^m))	(O(n))	Simple to implement	Exponential time, very slow
Dynamic Programming	(O(n \times m))	(O(n))	Efficient, avoids recomputation	Slightly more complex to implement

---

Conclusion

The Minimum Coin Change problem can be solved through backtracking, but the dynamic programming approach significantly improves the performance by leveraging a table to avoid redundant calculations. The dynamic programming approach brings the time complexity down from exponential to polynomial, making it feasible to solve larger instances of the problem.