Introduction to the Coin Change Problem
The Coin Change Problem is one of the most classic algorithmic challenges you will encounter in computer science and software engineering interviews. At its core, the problem asks: given a set of coin denominations and a target amount, what is the minimum number of coins needed to make up that amount? If the amount cannot be made, you should return an indication that no solution exists.
While the problem sounds simple, it has deep connections to dynamic programming, greedy algorithms, and combinatorial optimization. In this tutorial, we will walk through solving the Coin Change Problem in Go, starting from a naive recursive approach and building up to an efficient dynamic programming solution.
Understanding the Problem Statement
Before writing any code, let us clearly define the problem. You are given:
- An array of integers representing coin denominations, for example
[1, 2, 5]. - A target integer amount, for example
11.
Your task is to return the fewest number of coins needed to make up that amount. For the example above, the answer is 3 because 5 + 5 + 1 = 11. If the amount cannot be formed by any combination of the coins, return -1. You may assume that you have an infinite supply of each coin denomination.
Why the Coin Change Problem Matters
The Coin Change Problem is not just an academic exercise. It models real-world scenarios such as currency exchange systems, vending machine logic, resource allocation, and even certain scheduling problems. Understanding how to solve it efficiently teaches you the fundamentals of dynamic programming, a technique that appears everywhere from shortest-path algorithms to bioinformatics.
Moreover, the problem highlights an important lesson: a greedy approach does not always work. For example, with coins [1, 3, 4] and a target of 6, a greedy algorithm would pick 4 + 1 + 1 = 6 using three coins, but the optimal solution is 3 + 3 = 6 using only two coins. This is why dynamic programming is necessary.
Approach 1: Naive Recursion
The most intuitive way to solve the problem is through recursion. For each coin, we subtract its value from the target amount and recursively solve the smaller subproblem. The base case is when the amount becomes zero, meaning we have successfully formed the amount, or when it becomes negative, meaning this path is invalid.
package main
import (
"fmt"
"math"
)
func coinChangeRecursive(coins []int, amount int) int {
if amount == 0 {
return 0
}
if amount < 0 {
return -1
}
minCoins := math.MaxInt32
for _, coin := range coins {
result := coinChangeRecursive(coins, amount-coin)
if result >= 0 && result+1 < minCoins {
minCoins = result + 1
}
}
if minCoins == math.MaxInt32 {
return -1
}
return minCoins
}
func main() {
coins := []int{1, 2, 5}
amount := 11
fmt.Println(coinChangeRecursive(coins, amount)) // Output: 3
}
While this solution is correct, it has exponential time complexity. The same subproblems are computed repeatedly, leading to massive inefficiency for larger amounts. This is where memoization and dynamic programming come into play.
Approach 2: Top-Down Dynamic Programming with Memoization
To avoid recomputing the same subproblems, we can cache the results of each recursive call. This technique is called memoization. We use a map or an array to store the minimum coins needed for each amount we have already computed.
package main
import (
"fmt"
"math"
)
func coinChangeMemo(coins []int, amount int) int {
memo := make(map[int]int)
return helper(coins, amount, memo)
}
func helper(coins []int, amount int, memo map[int]int) int {
if amount == 0 {
return 0
}
if amount < 0 {
return -1
}
if val, ok := memo[amount]; ok {
return val
}
minCoins := math.MaxInt32
for _, coin := range coins {
result := helper(coins, amount-coin, memo)
if result >= 0 && result+1 < minCoins {
minCoins = result + 1
}
}
if minCoins == math.MaxInt32 {
memo[amount] = -1
} else {
memo[amount] = minCoins
}
return memo[amount]
}
func main() {
coins := []int{1, 3, 4}
amount := 6
fmt.Println(coinChangeMemo(coins, amount)) // Output: 2
}
This approach reduces the time complexity to O(amount * len(coins)) because each subproblem is solved only once. The space complexity is O(amount) for the memoization map plus the recursion stack.
Approach 3: Bottom-Up Dynamic Programming
The bottom-up approach eliminates recursion entirely. We build a table from 0 to amount, where each entry dp[i] represents the minimum number of coins needed to make amount i. We initialize dp[0] = 0 because zero coins are needed to make amount zero, and all other entries to a large sentinel value.
package main
import (
"fmt"
"math"
)
func coinChangeDP(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp {
dp[i] = math.MaxInt32
}
dp[0] = 0
for i := 1; i <= amount; i++ {
for _, coin := range coins {
if coin <= i && dp[i-coin]+1 < dp[i] {
dp[i] = dp[i-coin] + 1
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}
func main() {
coins := []int{1, 2, 5}
amount := 11
fmt.Println(coinChangeDP(coins, amount)) // Output: 3
}
This is the most commonly recommended solution in interviews. The outer loop iterates through every amount from 1 to the target, and the inner loop tries every coin. If the coin value is less than or equal to the current amount, we check whether using that coin produces a better result than what we already have.
Tracing Through an Example
Let us trace through the bottom-up solution with coins [1, 2, 5] and amount 11. The dp array starts as [0, INF, INF, ..., INF] with 12 entries. As we fill it in:
dp[1] = 1(use one coin of value 1)dp[2] = 1(use one coin of value 2)dp[3] = 2(use 2 + 1)dp[5] = 1(use one coin of value 5)dp[10] = 2(use 5 + 5)dp[11] = 3(use 5 + 5 + 1)
By the end, dp[11] holds the answer 3.
Approach 4: Tracking the Coins Used
Sometimes you need to know not just the minimum number of coins, but which coins were actually used. We can extend the bottom-up approach by maintaining an additional array that records the last coin used for each amount.
package main
import (
"fmt"
"math"
)
func coinChangeWithCoins(coins []int, amount int) (int, []int) {
dp := make([]int, amount+1)
used := make([]int, amount+1)
for i := range dp {
dp[i] = math.MaxInt32
used[i] = -1
}
dp[0] = 0
for i := 1; i <= amount; i++ {
for _, coin := range coins {
if coin <= i && dp[i-coin]+1 < dp[i] {
dp[i] = dp[i-coin] + 1
used[i] = coin
}
}
}
if dp[amount] == math.MaxInt32 {
return -1, nil
}
// Reconstruct the coins used
var result []int
remaining := amount
for remaining > 0 {
coin := used[remaining]
result = append(result, coin)
remaining -= coin
}
return dp[amount], result
}
func main() {
coins := []int{1, 2, 5}
amount := 11
count, used := coinChangeWithCoins(coins, amount)
fmt.Printf("Minimum coins: %d\n", count)
fmt.Printf("Coins used: %v\n", used) // Output: [1 5 5]
}
This version is especially useful in practical applications where you need to display or log the actual combination of coins chosen, not just the count.
Best Practices and Optimization Tips
Sort Coins for Early Termination
Sorting the coins array can help in certain variations of the problem. For example, if you want to try larger coins first in a hybrid greedy-dynamic approach, sorting gives you that flexibility. However, for the standard bottom-up DP, sorting is not strictly necessary.
Use a Sentinel Value Instead of math.MaxInt32
Using math.MaxInt32 can cause integer overflow issues if you add to it. A safer approach is to use amount + 1 as the sentinel, since the maximum possible number of coins needed is amount (using all 1-value coins). Any value greater than amount effectively means "unreachable."
func coinChangeDPSafe(coins []int, amount int) int {
max := amount + 1
dp := make([]int, amount+1)
for i := range dp {
dp[i] = max
}
dp[0] = 0
for i := 1; i <= amount; i++ {
for _, coin := range coins {
if coin <= i && dp[i-coin]+1 < dp[i] {
dp[i] = dp[i-coin] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
Handle Edge Cases Explicitly
Always handle edge cases such as an amount of zero, an empty coins array, or coins that cannot form the target. Defensive programming prevents panics and unexpected behavior in production code.
Benchmark Different Approaches
Go has a built-in benchmarking framework. If performance is critical, write benchmarks for the memoization and bottom-up approaches to determine which is faster for your specific input sizes. In most cases, the bottom-up approach is slightly faster due to the absence of recursion overhead.
Time and Space Complexity Analysis
For the bottom-up dynamic programming solution, the time complexity is O(amount * n) where n is the number of coin denominations. This is because we iterate over every amount from 1 to the target, and for each amount, we iterate over all coins.
The space complexity is O(amount) for the dp array. If you also track the coins used, the space complexity remains O(amount) because the used array has the same length as dp.
Compared to the naive recursive approach, which has exponential time complexity, the dynamic programming solution is a massive improvement and can handle amounts in the tens of thousands efficiently.
Conclusion
The Coin Change Problem is a foundational algorithmic challenge that every Go developer should understand. We explored multiple approaches, starting from a naive recursive solution and progressing to memoization and bottom-up dynamic programming. The bottom-up DP approach is generally the best choice due to its clarity, efficiency, and avoidance of recursion stack limits. By following best practices such as using safe sentinel values, handling edge cases, and optionally tracking the coins used, you can build a robust solution suitable for both interviews and production systems. Mastering this problem will give you a strong foundation in dynamic programming that you can apply to countless other algorithmic challenges.