Coin Change
Problem
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
Examples
Example 1
Input: coins = [1,5,10,25], amount = 30
Output: 2
Explanation: 25 + 5 = 30
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot make 3 from coin 2.
Constraints
- •
1 <= coins.length <= 12 - •
1 <= coins[i] <= 2^31 - 1 - •
0 <= amount <= 10^4
Hints
Hint 1
The brute-force recursive idea: for each amount, try EVERY coin, recursing on the remainder — correct, but the same sub-amounts get recomputed repeatedly across different branches, exponential blowup.
Hint 2
Build dp[0..amount] where dp[i] = min coins to make amount i, computed bottom-up so each sub-amount is solved exactly once.
Hint 3
dp[i] = min over every coin c <= i of (dp[i - c] + 1) — try using each coin last, and take whichever choice leaves the cheapest remainder.
Solutions
public int coinChangeBruteForce(int[] coins, int amount) {
int result = helper(coins, amount);
return result == Integer.MAX_VALUE ? -1 : result;
}
private int helper(int[] coins, int remaining) {
if (remaining == 0) return 0;
if (remaining < 0) return Integer.MAX_VALUE;
int best = Integer.MAX_VALUE;
for (int coin : coins) {
int sub = helper(coins, remaining - coin);
if (sub != Integer.MAX_VALUE) best = Math.min(best, sub + 1);
}
return best;
}Time: O(coins.length ^ amount) worst case · Space: O(amount) recursion depth