Coin Change Explained: Minimum Coins and Number of Ways

You solve the Coin Change problem by choosing between a 1D array for minimum coins and a nested loop structure for the number of ways. Greedy logic fails because it cannot backtrack when a local optimal choice prevents a global solution. Use dynamic programming to build your answer from smaller subproblems, ensuring you handle the state transitions correctly for each variation.

Why greedy fails

You might be tempted to pick the largest coin first to reach the target amount quickly. This works for standard currency systems like the Indian Rupee, where denominations are designed to be canonical. However, consider a coin set of {1, 3, 4} and a target of 6. A greedy approach picks 4, leaving a remainder of 2, which requires two 1-rupee coins for a total of three coins. The optimal solution is two 3-rupee coins. Greedy logic lacks the foresight to see that picking a smaller coin now might allow for a more efficient combination later. It commits to a path without considering the global minimum.

Minimum coins as unbounded knapsack

To find the minimum number of coins, treat the problem as an unbounded knapsack variation. You want to minimize the count for every value from 1 up to the target amount. Create an array dp of size target + 1 initialized to infinity, with dp[0] = 0. For each coin in your set, iterate through the dp array from the coin value up to the target. Update dp[i] = min(dp[i], dp[i - coin] + 1). This ensures that for every amount, you check if using the current coin results in fewer coins than the best solution found so far.

Counting ways with loop order

When the question asks for the number of ways to make change, the order of loops changes everything. You must iterate through the coins in the outer loop and the target amounts in the inner loop. This structure ensures you count combinations rather than permutations. If you swap the loops, you count the same set of coins in different orders, like {1, 2} and {2, 1}, as distinct ways. By fixing the coin in the outer loop, you force the algorithm to consider coins in a specific sequence, which naturally prevents duplicate counting.

A worked example

Let the coins be {1, 2} and the target be 3. Initialize dp array of size 4 as [1, 0, 0, 0]. Outer loop coin = 1: dp[1] += dp[0] -> 1 dp[2] += dp[1] -> 1 dp[3] += dp[2] -> 1 Outer loop coin = 2: dp[2] += dp[0] -> 1 + 1 = 2 dp[3] += dp[1] -> 1 + 1 = 2 The final value at dp[3] is 2, representing the combinations {1, 1, 1} and {1, 2}.

Rule of thumb for interviews

• Use a 1D array for both problems to keep space complexity at O(target).
• For minimum coins, use min in your transition and initialize with infinity.
• For number of ways, use sum in your transition and initialize dp[0] = 1.
• Always place the coin loop outside the target loop to count combinations.
• If the problem asks for permutations, swap the loops so the target is the outer loop.

DSA Tracker helps you practice these patterns until they become second nature. To solidify this, pick a problem like Coin Change 2 on a coding platform and trace the dp array update for a target of 5 with coins {1, 2, 5} on paper before writing the code.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Dynamic programming on Wikipedia.