Q. Given a sum of value S and infinite supply of coins each of value C = { C1, C2, .. , Cn}, how many ways can you make the change? The order of coins doesn’t matter.
For example, for S = 5 and S = {1,2}, there are three solutions: (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2) . So output should be 3. For S = 10 and C = {2, 5, 3, 6}, there are five solutions: (2,2,2,2,2), (2,2,3,3), (2,2,6), (2,3,5) and (5,5). So the output should be 5.
Yes, I agree; this question is hard. But can we simplify it to come up with a solution that will solve this tough one!
What if C was { 1 } and S was 10? Number of combinations possible is 1; Ten times 1 is the only way to form the sum 10. That was quick and easy, right? 😀
Lets take it to next level. This time, lets try with more coins: 1 and 2 and same sum: 10. Yes, many combinations flashed my mind too. Lets cross this bridge one step at a time. Lets first list out all the combinations
How do I convert this to a program!!! Lets walk through the process that happened in my brain when I wrote down those combinations.
- I took zero 2 and tried to form the remaining sum with all 1. I could use ten 1 to form the sum.
- I took one 2 and tried to form the rest of the sum with all 1.
- Took three 2 and got six 1
- Took four 2 and got four 1
- Took five 2 and got two 1
- Took six 2 and got zero 1
Good question (if this already came up in your mind)! what if I tried to find the count of 2 by giving values to number of 1. Lets work it out.
Both cases, I did nothing but iterate from 0 till a number which when multiplied with the chosen coin (2 in first case and 1 in second case) is larger than sum. In every step, I tried to form the remaining “sum” with rest of the denominations.
We encountered more steps than in the previous one but at the end it turned out to be the same number of combinations. Obvious! Trying out both ways helped us discover an optimization: Larger Denominations First. Lets shorten it to LDF 😉
So lets transform our knowledge to algorithm now. For that, lets set some terminologies.
Terminologies:
- D : All denominations(coins) in ascending order. Why sorting? Sorting is just to implement LDF (Larger Denominations First) and is optional.
- D[i] : value of i-th coin . Assume that index starts with 1.
- S : sum to be formed.
- F(i, S) : Returns the maximum combinations possible with first ‘i’ denominations to form sum ‘S’
- F(i, n, S) : Returns the maximum combinations possible with first ‘i’ denominations using i-th denomination ‘n’ times. This function is to find the maximum combinations possible with remaining denominations while keeping the count of i-th denomination to a particular value.
For our case where D = { 1, 2 } and S = 10:
- F(2, 10) should give us 6 since there are 6 different ways to form a sum of 10 with 1 and 2
- F(1, 10) should give 1.
- F(2, 0, 10) should give 1
- F(2, 1, 10) should give 1
- F(2, 2, 10) should give 1
- F(2, 3, 10) should give 1
- F(2, 4, 10) should give 1
- F(2, 5, 10) should give 1
- F(2, 6, 10) should give 0
- F(2, 7, 10) should give 0
Lets try to define F(i, S) in terms of F(i, n, S).
This is nothing but mathematical representation of a for-loop with variable x iterating from 0 to (S/D[i]), beyond which the x*D[i] will be greater than S.
Now we should define F(i, n, S). As stated before, F(i, n, S) is the maximum number of combinations possible with D[i] used ‘n’ times. With the number of D[i] fixed to n, we just need to iterate through the rest of the coins. So it can be defined as
It is a recursive function which reduces the sum by D[i]*n and finds the maximum combinations with rest of the coins. But what should it do when it reaches the last denomination? It should be able to divide the sum without any remainder; if not, there is no possible combination with the chosen numbers. Simple!
Now, lets try to apply our new algorithm.
F(2, 10) = F(2, 0, 10) +
F(2, 1, 10) +
F(2, 2, 10) +
F(2, 3, 10) +
F(2, 4, 10) +
F(2, 5, 10)
= F(1, 0, 10) + F(1, 2, 10) + F(1, 3, 10) + F(1, 4, 10) + F(1, 5, 10) + F(1, 6, 10) + F(1, 7, 10) ++ F(1, 8, 10) + F(1, 9, 10) + F(1, 10, 10) + F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) +
F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) +
F(1, 0, 6) + F(1, 1, 6) + F(1, 2, 6) + F(1, 3, 6) + F(1, 4, 6) + F(1, 5, 6) + F(1, 6, 6) +
F(1, 0, 4) + F(1, 1, 4) + F(1, 2, 4) + F(1, 3, 4) + F(1, 4, 4) +
F(1, 0, 2) + F(1, 1, 2) + F(1, 2, 2) +
F(1, 0, 0)
= 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 1 +
0 + 1 +
1
= 6
That worked!
Lets write some Java now..
package fun.puzzles;
import java.util.Arrays;
import java.util.List;
public class CoinCombinationsPuzzle {
private final List<Integer> coins;
public CoinCombinationsPuzzle(List<Integer> coins) {
this.coins = coins;
}
public int maximumPossibleCombinations(int numOfCoins, Integer sum) {
coins.sort(null);
int maxIteration = sum/coins.get(numOfCoins);
int maxPossibleCombinations = 0;
for (int i = 0; i <= maxIteration; i++) {
maxPossibleCombinations += maximumPossibleCombinations(numOfCoins, i, sum);
}
return maxPossibleCombinations;
}
public int maximumPossibleCombinations(int numOfCoins, int count, Integer sum) {
// safety check
if (numOfCoins < 0) { return 0; }
if (numOfCoins < 1) {
if (count * coins.get(numOfCoins) == sum) {
return 1;
}
else {
return 0;
}
}
// Reduce the fixed denomination from sum
sum -= (count * coins.get(numOfCoins));
int maxIteration = sum/coins.get(numOfCoins-1);
int maxPossibleCombinations = 0;
for (int i = 0; i <= maxIteration; i++) {
maxPossibleCombinations += maximumPossibleCombinations(numOfCoins-1, i, sum);
}
return maxPossibleCombinations;
}
public int maximumPossibleCombinations(Integer sum) {
return maximumPossibleCombinations(coins.size()-1, sum);
}
public void printMaximumPossibleCombinations(Integer sum) {
System.out.printf("Coins: %-50s Sum: %-5d MaximumPossibleCombinations: %-5d\n",
coins, sum, maximumPossibleCombinations(coins.size()-1, sum));
}
public static void main(String[] args) {
List<Integer> coins;
CoinCombinationsPuzzle ccp;
coins = Arrays.asList(1, 2);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(5);
coins = Arrays.asList(1, 2);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(10);
coins = Arrays.asList(1, 2, 3);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(100);
coins = Arrays.asList(1, 2, 5, 10);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(1074);
}
}
Output:
This solution can still be optimized by caching the results of recursive method: maximumPossibleCombinations(int numOfCoins, int count, Integer sum)
WikiSree 