Coin Change Permutations
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 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.
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 <= 20Sample Input
0 <= n1, n2, .. n elements <= 20
0 <= amt <= 30
4Sample Output
2
3
5
6
7
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)
-
Asked in Companies
-
Related Topics
