Coin Change
Question
There is a coin machine that gives you infinite amount of coins of certain values. Given this list of values and a total target value, return the fewest coins needed to sum up to the target.
If there are no combinations of coints that can sum up to the target, return -1.
Input: coins = [1, 2, 5], target = 11
Output: 3
11 = 5 + 5 + 1
The fewest number of coins needed to sum up to 11 is 3 coins. We can reach the target with these combinations:
- 11 coins: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
- 3 coins: 5 + 5 + 1
Input: coins = [2, 5, 10], target = 20
Output: 2
The fewest number of coins needed to sum up to 20 is 2 coins. We can reach the target with these combinations:
- 10 coins: 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
- 6 coins: 10 + 2 + 2 + 2 + 2 + 2
- 4 coins: 5 + 5 + 5 + 5
- 3 coins: 10 + 5 + 5
- 2 coins: 10 + 10
Input: coins = [2], target = 3
Output: -1
There are no combinations of coins that will sum up to 3 in this case.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Login or signup to save your code.
Uh oh... looks like you don't yet have access.
Not sure what this unlocks? Check out a free pattern section.
Example solution
Complexity
