{"id":"8ed46ca7-7a42-451c-a4e1-c45f7a458201","name":"Coin Change Permutations","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 permutations 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 permutations and not combinations 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 3 and not 1.","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;= 20\r\n0 &lt;= n1, n2, .. n elements &lt;= 20\r\n0 &lt;= amt &lt;= 30","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nint CCP(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 CCP(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":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nint CCP(vector<int> coins, int amt, vector<int> dp) {\r\n\r\n// write your code here\r\n\r\n}\r\n\r\nint main() {\r\n int n;\r\n cin >> n;\r\n vector<int> coins(n, 0);\r\n for (int i = 0; i < coins.size(); i++) {\r\n cin >> coins[i];\r\n }\r\n int amt;\r\n cin >> amt;\r\n vector<int> dp(amt + 1, 0);\r\n CCP(coins, amt, dp);\r\n\r\n}"}},"points":10,"difficulty":"medium","sampleInput":"4\r\n2\r\n3\r\n5\r\n6\r\n7","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/yc0LunmJA1A?start=0&end=171","hints":[],"associated":[{"id":"9fe4ab7e-ace5-45af-a2f2-6ab7dff20b90","name":"You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________","slug":"you-are-given-infinite-coins-of-denominations-v1-v2-v3-vn-and-a-sum-s-the-coin-change-problem-is-to-find-the-minimum-number-of-coins-required-to-get-the-sum-s-this-problem-can-be-solved-using","type":4},{"id":"b8a3ab5c-934b-4d48-9d81-49368435c81c","name":"You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?","slug":"you-are-given-infinite-coins-of-denominations-3-5-7-which-of-the-following-sum-cannot-be-achieved-using-these-coins","type":4},{"id":"ef78aa8c-ae97-4f08-b43b-3c8b69d9c4a9","name":"You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?","slug":"you-are-given-infinite-coins-of-denominations-1-3-4-what-is-the-minimum-number-of-coins-required-to-achieve-a-sum-of-7","type":4},{"id":"f5b79424-3970-4faa-aadb-848b37a014ea","name":"what is the difference this this problem ans target sum subsets?","slug":"what-is-the-difference-this-this-problem-ans-target-sum-subsets","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":"f5a4217e-757b-4c86-8f8d-edf4a9b84d96","name":"Coin Change Permutations","slug":"coin-change-permutations","type":1}],"next":{"id":"14689e99-e125-4017-a53b-2f71c54bf5ab","name":"Coin Change - Permutations","type":3,"slug":"coin-change-permutations"},"prev":{"id":"7ea0cb66-24eb-4901-a272-9f3e4948f98a","name":"Coin Change Combination","type":3,"slug":"coin-change-combination"}}}

Coin Change Permutations

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.

{"id":"8ed46ca7-7a42-451c-a4e1-c45f7a458201","name":"Coin Change Permutations","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 permutations 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 permutations and not combinations 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 3 and not 1.","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;= 20\r\n0 &lt;= n1, n2, .. n elements &lt;= 20\r\n0 &lt;= amt &lt;= 30","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nint CCP(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 CCP(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":"#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nint CCP(vector<int> coins, int amt, vector<int> dp) {\r\n\r\n// write your code here\r\n\r\n}\r\n\r\nint main() {\r\n int n;\r\n cin >> n;\r\n vector<int> coins(n, 0);\r\n for (int i = 0; i < coins.size(); i++) {\r\n cin >> coins[i];\r\n }\r\n int amt;\r\n cin >> amt;\r\n vector<int> dp(amt + 1, 0);\r\n CCP(coins, amt, dp);\r\n\r\n}"}},"points":10,"difficulty":"medium","sampleInput":"4\r\n2\r\n3\r\n5\r\n6\r\n7","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/yc0LunmJA1A?start=0&end=171","hints":[],"associated":[{"id":"9fe4ab7e-ace5-45af-a2f2-6ab7dff20b90","name":"You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________","slug":"you-are-given-infinite-coins-of-denominations-v1-v2-v3-vn-and-a-sum-s-the-coin-change-problem-is-to-find-the-minimum-number-of-coins-required-to-get-the-sum-s-this-problem-can-be-solved-using","type":4},{"id":"b8a3ab5c-934b-4d48-9d81-49368435c81c","name":"You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?","slug":"you-are-given-infinite-coins-of-denominations-3-5-7-which-of-the-following-sum-cannot-be-achieved-using-these-coins","type":4},{"id":"ef78aa8c-ae97-4f08-b43b-3c8b69d9c4a9","name":"You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?","slug":"you-are-given-infinite-coins-of-denominations-1-3-4-what-is-the-minimum-number-of-coins-required-to-achieve-a-sum-of-7","type":4},{"id":"f5b79424-3970-4faa-aadb-848b37a014ea","name":"what is the difference this this problem ans target sum subsets?","slug":"what-is-the-difference-this-this-problem-ans-target-sum-subsets","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":"f5a4217e-757b-4c86-8f8d-edf4a9b84d96","name":"Coin Change Permutations","slug":"coin-change-permutations","type":1}],"next":{"id":"14689e99-e125-4017-a53b-2f71c54bf5ab","name":"Coin Change - Permutations","type":3,"slug":"coin-change-permutations"},"prev":{"id":"7ea0cb66-24eb-4901-a272-9f3e4948f98a","name":"Coin Change Combination","type":3,"slug":"coin-change-combination"}}}
plane

Editor


Loading...

Coin Change Permutations

medium

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.

Constraints

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

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

5

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode