Coin Change

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a list of coin values and a target amount, return the smallest number of coins that add up to exactly that amount, or −1 if it can't be done. You have an unlimited supply of each coin value.

    This is the problem most interviewers use to check whether you can move from "try the obvious greedy" to a real dynamic programming recurrence. Original problem: LeetCode 322.

    Example

    With coins 1, 3, 4 and amount 6, the best answer is 3 + 3; taking the biggest coin first gives 4 + 1 + 1.
    With coins 1, 3, 4 and amount 6, the best answer is 3 + 3; taking the biggest coin first gives 4 + 1 + 1.
    Input:  coins = [1, 3, 4], amount = 6
    Output: 2          # 3 + 3
    Input:  coins = [2], amount = 3
    Output: -1         # odd amounts can't be made from 2s
    Input:  coins = [1], amount = 0
    Output: 0

    Constraints (assumed)

    • 1 ≤ number of coins ≤ 12, 1 ≤ coin value ≤ 2³¹ − 1.
    • 0 ≤ amount ≤ 10,000.

    What this question tests

    • Recognising that greedy fails for arbitrary coin systems, and proving it with a small counterexample.
    • Defining a DP state and recurrence in words before coding.
    • Handling "impossible" cleanly, without integer overflow.

    Questions to ask first

    1. Is the supply of each coin unlimited? (Here: yes. If each coin can be used once, it becomes a 0/1 knapsack.)
    2. What should I return when the amount can't be made? (Here: −1.)
    3. Can the amount be 0? (Yes: zero coins.)
    4. How large is the amount? O(amount) memory must be acceptable.