/**
* 518. Coin Change 2
* Question asks to find number of combinations of coins that can be used to calculate a given amount
* You are given coins of different denominations and a total amount of money.
* Write a function to compute the number of combinations that make up that amount.
* You may assume that you have infinite number of each kind of coin.
* Example 1:
* Input: amount = 5, coins = [1, 2, 5]
* Output: 4
* Explanation: there are four ways to make up the amount:
* 5=5
* 5=2+2+1
* 5=2+1+1+1
* 5=1+1+1+1+1
*/
See my solution for this code change here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/CoinChangeTwo.java
See the approach to solving this problem below:
Logic below is based on dynamic programming where we aggregate possibilities per count from index 0 to the desired amount. Each coin will augment the previously calculated possibilities by the increased possibility due to the current coin. Once all coins have been processed the amount index will contain the desired number value – number of ways to get to the desired amount.
- Create an array of size equal to desired amount + 1. +1 to handle the sentinel of ‘0’ while setting the value in amount array for ‘0’ as 1.
- For each coin iterate from coin value to desired amount while adding the value in current amount index – coin value to current index. We start from the coin value because starting from less than coin value leads to prior amount less than 0 which isn’t possible. For example, for coin 5, we start from index 5 because values less than 5 lead to prior value less than 0 which is possible as starting index logically is 0.
See below table for a visual explanation of the algorithm with target amount 10 using coins 2,5 & 10.
Here is the code:
int change(int amount, int [] coins) {
int [] change = new int[amount+1];
change[0]=1;
for (int coin : coins) {
for(int i =coin; i <= amount; i++) {
change[i] += change[i-coin];
}
}
return change[amount];
}