Coin Change
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

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
- Is the supply of each coin unlimited? (Here: yes. If each coin can be used once, it becomes a 0/1 knapsack.)
- What should I return when the amount can't be made? (Here: −1.)
- Can the amount be 0? (Yes: zero coins.)
- How large is the amount? O(amount) memory must be acceptable.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.