Description:
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1
.
coins = [1, 2, 5], amount = 11, return 3 (11 = 5 + 5 + 1)
coins = [2], amount = 3, return -1.
Code:
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int min = -1;
for (int coin : coins) {
int currentMin = coinChange(coins, amount - coin);
// if amount is less than coin value
if (currentMin >= 0) {
min = min < 0 ? currentMin : Math.min(currentMin, min);
}
}
return min < 0 ? -1 : min + 1;
}
}
Questions:
This question has slight deviation from normal one where we just need to return 0
, returning -1
got me confused and I found it really hard to think in terms of recursion and handling edge cases.
PS: The solution works perfectly.
-1
to stop the recursion? \$\endgroup\$ – πάντα ῥεῖ Apr 16 '18 at 20:04-1
. \$\endgroup\$ – CodeYogi Apr 16 '18 at 20:08