Coin Change Combination
1. You are given a number n, representing the count of coins.Input Format
2. You are given n numbers, representing the denominations of n coins.
3. You are given a number "amt".
4. You are required to calculate and print the number of combinations of the n coins using which the
amount "amt" can be paid.
Note1 > You have an infinite supply of each coin denomination i.e. same coin denomination can be
used for many installments in payment of "amt"
Note2 > You are required to find the count of combinations and not permutations i.e.
2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same
combination. You should treat them as 1 and not 3.
A number nOutput Format
n1
n2
.. n number of elements
A number amt
A number representing the count of combinations of coins which can be used to pay the amount "amt"Question Video
1 <= n <= 30Sample Input
0 <= n1, n2, .. n elements <= 20
0 <= amt <= 50
4Sample Output
2
3
5
6
7
2

Editorial
Consider a scenario where we have coins of 2, 3, 5 and we want to form the sum = 7
This can be achieved by 3 different ways as follows
1. To all the combinations of sum = 5(i.e., 72) adding a coin with value 2 will form the new combination of sum = 7
2. To all the combinations of sum = 4(i.e., 73) adding a coin with value 3 will form the new combination of sum = 7
3. To all the combinations of sum = 2(i.e., 75) adding a coin with value 5 will form the new combination of sum = 7
On generalising the above thing,
Let arr be the array where arr[ i ] contains the value of the ith coin.
Let count(arr, n, amt) represent the Number of the combinations of coins in the arr whose sum is amt
count (arr, n, amt) = SUM OF (count(arr, n, amt  cv)) FOR ALL coin values cv belongs to arr
Note: To ensure the combinations are counted not permutations we will introduce coins one by one. (Will understand better after dry run of an example explained below)
Tabulation:
Given an coins array of size n , amount amt
1.Create a dp table to store the integer values of size amt + 1
2.Meaning: dp[i] will contain the number of combinations to form an amount = i
3.Required answer will be in dp[ amt ]
4.Base conditions: i = 0 => To form an amount = 0
As amount = 0 has one combination dp[ i ] = 1 for i = 0
5.Recursive equation:
for each coin value cv in coins: //INTRODUCING COINS ONE BY ONE
for curr_amt from 1 to amt:
if(curr_amt >= cv):
dp[curr_amt] = dp[ curr_amt  cv ]
Example:
Let amt = 10 and coins[3] = { 2, 3, 5 } i.e.,To form 10 with coins of 2, 3, 5 Initial dp table of size 11 indexed from 0 to 10: dp[ 0 ] = 1 as amount = 0 has one combination.
Introducing coin 2:dp[ i ] += dp[ i2 ] only when i >= 2
After above calculation:
Introducing coin 3:dp[ i ] += dp[ i3 ] only when i >= 3
After above calculation:
Introducing coin 5:dp[ i ] += dp[ i5 ] only when i >= 5
After above calculation:
Finally after introducing coins one by one required ans = dp[ amt ] = dp[ 10 ] = 4
Thus there are 4 combinations to form an amount of 10.
Why Introducing coins one by one will ensure the count of combinations not permutations:
As the coins are introduced one by one they are in order i.e., in above example all the combinations 2s followed by 3s then followed by 5s. There will not be a possibility of occurrence of 2 after introducing 3. Thus combinations is guaranteed.
int coin_change_combination(vector
&coins, int n, int tar_amt) { vector
dp(tar_amt + 1, 0); //dp[i] ==> no of combinations to form the amount = i; dp[0] = 1; //amount = 0 has one combination i.e., selecting none. for (int i = 1; i <= n; i++) { //Introducing coins one by one //Ensuring the combinations not permutations int coin_val = coins[i  1]; //ith coin will have index i1 for (int amt = coin_val; amt <= tar_amt; amt++) { dp[amt] += dp[amt  coin_val]; } } return dp[tar_amt]; }
java false
Time complexity:
Each cell of the dp table takes O( 1 ) time
Total number of cell in dp table = amt + 1
Total time = (amt + 1) * O( 1 ) = O(amt)

Asked in Companies

Related Topics