Coin Change

Problem statement

You have coins of given denominations, unlimited of each. Return the fewest coins that sum to amount. If nothing works, return -1.

Example:

Input:

coins = [1, 2, 5], amount = 11

Expected output:

3

Why: 5 + 5 + 1. Four 2s and three 1s also make 11, but they use more coins.

A miss: coins = [2], amount = 3 → -1.

Practice on LeetCode: Coin Change

What we are asking

The question is not “can I make this amount.” It is “what is the shortest list of coins that does.”

dfs(target) is the fewest coins that make target. You try every denomination once as the next coin:

dfs(target) = 1 + min(dfs(target - coin) for each coin)
dfs(0) = 0
dfs(negative) = impossible

On 11 with {1, 2, 5}:

dfs(11) = 1 + min(dfs(10), dfs(9), dfs(6))
dfs(6)  = 1 + min(dfs(5), dfs(4), dfs(1))
dfs(5)  = 1        // one 5

That path is 5, then 5, then 1 — three coins. Other branches are longer and lose the min.

Why greedy is wrong

Biggest coin first looks right on [1, 2, 5]. It is not a rule.

coins = [1, 3, 4], amount = 6: greedy takes 4 + 1 + 1 (three coins). 3 + 3 is two. The large coin steals the pairing that would have been cheaper.

So you have to try every next coin. That tree shares remainders — dfs(6) shows up under both 11 - 5 and other prefixes. There are only amount + 1 remainders. Remember each one.

Bottom-up is the same recurrence in an array: dp[x] = fewest coins for x, start dp[0] = 0, relax dp[x] = min(dp[x], dp[x - coin] + 1).

Golang Solution

A map from remaining amount to fewest coins. math.MaxInt is “impossible.” Skip that child so res+1 does not overflow. If the top call is still MaxInt, return -1.

Time: O(amount · k) — k is the number of denominations
Space: O(amount) — memo, plus recursion depth in the worst case

import "math"

func coinChange(coins []int, amount int) int {
    memo := map[int]int{}

    var dfs func(int) int

    dfs = func(target int) int {
        if target == 0 {
            return 0
        }
        if target < 0 {
            return math.MaxInt
        }

        if v, ok := memo[target]; ok {
            return v
        }

        ans := math.MaxInt

        for _, coin := range coins {
            res := dfs(target - coin)
            if res != math.MaxInt {
                ans = min(ans, res+1)
            }
        }

        memo[target] = ans
        return ans
    }

    ans := dfs(amount)

    if ans == math.MaxInt {
        return -1
    }

    return ans
}

amount == 0 is 0 coins — you are already done. Impossible remainders are stored too (MaxInt), so a dead amount is not searched twice.