{"id":"4e55692a-2da9-4539-82cc-e27e23feec48","name":"Coin Change Combination","description":"1. You are given a number n, representing the count of coins.\r\n2. You are given n numbers, representing the denominations of n coins.\r\n3. You are given a number \"amt\".\r\n4. You are required to calculate and print the number of combinations of the n coins using which the \r\n amount \"amt\" can be paid.\r\n\r\nNote1 -> You have an infinite supply of each coin denomination i.e. same coin denomination can be \r\n used for many installments in payment of \"amt\"\r\nNote2 -> You are required to find the count of combinations and not permutations i.e.\r\n 2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same \r\n combination. You should treat them as 1 and not 3.","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number amt","outputFormat":"A number representing the count of combinations of coins which can be used to pay the amount \"amt\"","constraints":"1 &lt;= n &lt;= 30\r\n0 &lt;= n1, n2, .. n elements &lt;= 20\r\n0 &lt;= amt &lt;= 50","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nint coinchangecombination(vector<int> coins, int amt, vector<int> dp) {\n \n// write your code here\n\n}\n\nint main() {\n int n;\n cin >> n;\n vector<int> coins(n, 0);\n for (int i = 0; i < coins.size(); i++) {\n cin >> coins[i];\n }\n int amt;\n cin >> amt;\n vector<int> dp(amt + 1, 0);\n coinchangecombination(coins, amt, dp);\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def ccp(coins,amt,dp):\n # write your code here\n \nn = int(input())\ncoins = [0]*n\n\nfor i in range(0,len(coins)):\n x = int(input())\n coins[i] = x\n\namt = int(input())\n\ndp = [0]*(amt+1)\n\nccp(coins,amt,dp)"}},"points":10,"difficulty":"easy","sampleInput":"4\r\n2\r\n3\r\n5\r\n6\r\n7","sampleOutput":"2","questionVideo":"https://www.youtube.com/embed/Ph1EB07Q4pA","hints":[],"associated":[{"id":"350a94d3-b4b0-4ed4-86da-7f8f11c405c3","name":"What will be the size of the storage array for the given array of size n?","slug":"what-will-be-the-size-of-the-storage-array-for-the-given-array-of-size-n","type":4},{"id":"40e18c01-148b-473a-a75c-1eaa0dd87b9b","name":"what is the meaning of the cell?","slug":"what-is-the-meaning-of-the-cell","type":4},{"id":"ff555ceb-1157-48d6-ae6f-e8827f470dd6","name":"what will be the value of the first index in storage array?","slug":"what-will-be-the-value-of-the-first-index-in-storage-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"66e4763d-5af1-4388-89fb-828618e75a30","name":"Coin Change Combination","slug":"coin-change-combination","type":1}],"next":{"id":"7ea0cb66-24eb-4901-a272-9f3e4948f98a","name":"Coin Change Combination","type":3,"slug":"coin-change-combination"},"prev":{"id":"f7674b46-22f3-44e7-8c6b-c11a7c1cfeba","name":"Target Sum Subsets - DP","type":3,"slug":"target-sum-subsets-dp"}}}

Coin Change Combination

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.

{"id":"4e55692a-2da9-4539-82cc-e27e23feec48","name":"Coin Change Combination","description":"1. You are given a number n, representing the count of coins.\r\n2. You are given n numbers, representing the denominations of n coins.\r\n3. You are given a number \"amt\".\r\n4. You are required to calculate and print the number of combinations of the n coins using which the \r\n amount \"amt\" can be paid.\r\n\r\nNote1 -> You have an infinite supply of each coin denomination i.e. same coin denomination can be \r\n used for many installments in payment of \"amt\"\r\nNote2 -> You are required to find the count of combinations and not permutations i.e.\r\n 2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same \r\n combination. You should treat them as 1 and not 3.","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number amt","outputFormat":"A number representing the count of combinations of coins which can be used to pay the amount \"amt\"","constraints":"1 &lt;= n &lt;= 30\r\n0 &lt;= n1, n2, .. n elements &lt;= 20\r\n0 &lt;= amt &lt;= 50","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nint coinchangecombination(vector<int> coins, int amt, vector<int> dp) {\n \n// write your code here\n\n}\n\nint main() {\n int n;\n cin >> n;\n vector<int> coins(n, 0);\n for (int i = 0; i < coins.size(); i++) {\n cin >> coins[i];\n }\n int amt;\n cin >> amt;\n vector<int> dp(amt + 1, 0);\n coinchangecombination(coins, amt, dp);\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def ccp(coins,amt,dp):\n # write your code here\n \nn = int(input())\ncoins = [0]*n\n\nfor i in range(0,len(coins)):\n x = int(input())\n coins[i] = x\n\namt = int(input())\n\ndp = [0]*(amt+1)\n\nccp(coins,amt,dp)"}},"points":10,"difficulty":"easy","sampleInput":"4\r\n2\r\n3\r\n5\r\n6\r\n7","sampleOutput":"2","questionVideo":"https://www.youtube.com/embed/Ph1EB07Q4pA","hints":[],"associated":[{"id":"350a94d3-b4b0-4ed4-86da-7f8f11c405c3","name":"What will be the size of the storage array for the given array of size n?","slug":"what-will-be-the-size-of-the-storage-array-for-the-given-array-of-size-n","type":4},{"id":"40e18c01-148b-473a-a75c-1eaa0dd87b9b","name":"what is the meaning of the cell?","slug":"what-is-the-meaning-of-the-cell","type":4},{"id":"ff555ceb-1157-48d6-ae6f-e8827f470dd6","name":"what will be the value of the first index in storage array?","slug":"what-will-be-the-value-of-the-first-index-in-storage-array","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"66e4763d-5af1-4388-89fb-828618e75a30","name":"Coin Change Combination","slug":"coin-change-combination","type":1}],"next":{"id":"7ea0cb66-24eb-4901-a272-9f3e4948f98a","name":"Coin Change Combination","type":3,"slug":"coin-change-combination"},"prev":{"id":"f7674b46-22f3-44e7-8c6b-c11a7c1cfeba","name":"Target Sum Subsets - DP","type":3,"slug":"target-sum-subsets-dp"}}}
plane

Editor

Loading...

Coin Change Combination

easy

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.

Constraints

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

Format

Input

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

Output

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

Example

Sample Input

4 2 3 5 6 7

Sample Output

2

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode