# Coin Change Permutations

#### 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 permutations 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 permutations and not combinations 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 3 and not 1.`
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 <= 200 <= n1, n2, .. n elements <= 200 <= amt <= 30`
Sample Input
`423567`
Sample Output
`5`

• 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 permutations of sum = 5(i.e., 7-2) adding a coin with value 2 at the end(or at the beginning) will form the new permutation of sum = 7

2. To all the permutations of sum = 4(i.e., 7-3) adding a coin with value 3 at the end(or at the beginning) will form the new permutations of sum = 7

3. To all the permutations of sum = 2(i.e., 7-5) adding a coin with value 5 at the end(or at the beginning) will form the new permutations 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 permutations 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: As we won't be introducing coins one by one, all the permutations will be counted.

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 permutations 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 permutation dp[ i ] = 1 for i = 0

5.Recursive equation:

for curr_amt from 1 to amt:

for each coin value cv in coins:

if(curr_amt >= cv):

dp[curr_amt] = dp[ curr_amt - cv ]

Example: Let amt = 7 and coins[3] = { 2, 3, 5 } i.e.,To form 7 with coins of 2, 3, 5

Initial dp table of size 8 indexed from 0 to 7:

dp[ 0 ] = 1 as amount = 0 has one combination.

Calculating dp[ 1 ]

As all coin values are greater than 1 => dp[ 1 ] = 0

Calculating dp[ 2 ]

dp[ 2]  = dp[ 2-2 ] = dp[ 0 ]

Calculating dp[ 3 ]

dp[ 3]  = dp[ 3-2 ] + dp[ 3-3 ] = dp[ 1 ] + dp[ 0 ]

Calculating dp[ 4 ]

dp[ 4]  = dp[ 4-2 ] + dp[ 4-3 ] = dp[ 2 ] + dp[ 1 ]

Calculating dp[ 5 ]

dp[ 5 ]  = dp[ 5-2 ] + dp[ 5-3 ] + dp[ 5-5 ] = dp[ 3 ] + dp[ 2 ]

Calculating dp[ 6 ]

dp[ 6 ]  = dp[ 6-2 ] + dp[ 6-3 ] + dp[ 6-5 ] = dp[ 4 ] + dp[ 3 ] + dp[ 1 ]

Calculating dp[ 7 ]

dp[ 7 ]  = dp[ 7-2 ] + dp[ 7-3 ] + dp[ 7-5 ] = dp[ 5 ] + dp[ 4 ]  + dp[ 2 ]

Final dp table:

Required answer is dp[ amt ] = dp[ 7 ] = 5

Thus there are 5 permutations to form amount 7.

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