# Coin Change Combination #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`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 nn1n2.. n number of elementsA 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 <= 300 <= n1, n2, .. n elements <= 200 <= amt <= 50`
Sample Input
`423567`
Sample Output
`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., 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 = { 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 = 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)

• Related Topics

Run

Run
Id Name