Given different denominations of coins and a total amount, find the minimum number of coins that make up that amount. If that amount cannot be made up by any combination of the coins, return -1.
Example:
int[] coins = {1, 2, 5};
int amount = 11;
Outputs:
3 (because 11 = 5 + 5 + 1)
Solution:
This problem is similar to combination sum
public int CoinChange(int[] coins, int amount) {
int result = CoinChangeRecursive(coins, amount);
return result == int.MaxValue ? -1 : result;
}
private int CoinChangeRecursive(int[] coins, int amount) {
// Base cases
if (amount == 0) return 0;
if (amount < 0) return int.MaxValue;
int minCoins = int.MaxValue;
foreach (var coin in coins) {
int result = CoinChangeRecursive(coins, amount - coin);
if (result != int.MaxValue) {
minCoins = Math.Min(minCoins, result + 1);
}
}
return minCoins;
}
This problem is similar to combination sum
Example 1:
Input:
candidates = [2,3,6,7], target = 7
Output:
[[2,2,3],[7]]
public class Solution {
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}
public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result)
{
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));
for (int i = start; i < cand.Length; i++)
{
list.Add(cand[i]);
BackTrack(cand, i, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}