Coin Change
Medium · Dynamic Programming · Array · Dynamic Programming · Breadth-First Search
Problem
Given coin denominations coins and a target amount, return the fewest coins needed to make that amount exactly. Return -1 if it cannot be made.
You have an unlimited supply of every denomination.
Examples
Input: coins = [1,2,5], amount = 11 Output: 3
5 + 5 + 1.
Input: coins = [2], amount = 3 Output: -1
Odd amounts are unreachable with only 2s.
Input: coins = [1], amount = 0 Output: 0
Zero coins make zero.
Constraints
- 1 <= len(coins) <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
Approaches
- Top-down memoised recursion — time O(amount · len(coins)), space O(amount)
Related problems
Start free on Cariara · Coding problems · System design studio
