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:
 Pick the current coin and subtract its value from the amount.
 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
.

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.
 Set

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 5coin.dp[10]
becomes 2 (since we can use two 5coins), anddp[11]
becomes 3 (two 5coins and one 1coin).
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.