Coin Change Combination

Prev Next

1. You are given a number n, representing the count of coins.
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.

Input Format

A number n
n1
n2
.. n number of elements
A number amt

Output Format

A number representing the count of combinations of coins which can be used to pay the amount "amt"

Question Video

Constraints

1 <= n <= 30
0 <= n1, n2, .. n elements <= 20
0 <= amt <= 50

Sample Input

Sample Output

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., 7-2) adding a coin with value 2 will form the new combination of sum = 7
2. To all the combinations of sum = 4(i.e., 7-3) adding a coin with value 3 will form the new combination of sum = 7
3. To all the combinations of sum = 2(i.e., 7-5) 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[ i-2 ] only when i >= 2
After above calculation:
Introducing coin 3:dp[ i ] += dp[ i-3 ] only when i >= 3
After above calculation:
Introducing coin 5:dp[ i ] += dp[ i-5 ] 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 i-1
                                        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