{"id":"7f434d28-aaf9-4bb1-9bbd-859b8924f620","name":"Coin Change - Combinations - 2","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 combinations of the n coins (same coin can be used \r\n again any number of times) using which the amount \"amt\" can be paid.\r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number amt","outputFormat":"Check the sample output and question video","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 <bits/stdc++.h>\nusing namespace std;\n void coinChange(int i, vector<int>&coins, int amtsf, int tamt, string asf) \n {\n // write your code here\n if (i == coins.size()) {\n if (amtsf == tamt) {\n cout<<asf<<\".\"<<endl;\n }\n return;\n }\n \n for (int j = tamt / coins[i]; j > 0; j--) {\n string pasf = \"\";\n for(int k = 0; k < j; k++){\n pasf += to_string(coins[i]) + \"-\";\n }\n coinChange(i + 1, coins, amtsf + coins[i]* j, tamt, asf+pasf+\"\");\n }\n coinChange(i + 1, coins, amtsf, tamt, asf);\n \n }\n int main()\n {\n int n;\n cin>>n;\n vector<int> coins(n);\n for(int i=0;i<n;i++)\n {\n cin>>coins[i];\n }\n int amt;\n cin>>amt;\n string ans=\"\";\n coinChange(0, coins, 0, amt, ans);\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void coinChange(int i, int[] coins, int amtsf, int tamt, String asf) {\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] coins = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n coins[i] = Integer.parseInt(br.readLine());\r\n }\r\n int amt = Integer.parseInt(br.readLine());\r\n coinChange(0, coins, 0, amt, \"\");\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n2\r\n3\r\n5\r\n6\r\n7\r\n12","sampleOutput":"2-2-2-2-2-2-.\r\n2-2-2-3-3-.\r\n2-2-2-6-.\r\n2-2-3-5-.\r\n2-3-7-.\r\n2-5-5-.\r\n3-3-3-3-.\r\n3-3-6-.\r\n5-7-.\r\n6-6-.","questionVideo":"https://www.youtube.com/embed/onUoUZDtak8?end=242","hints":[],"associated":[],"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":"082986ae-d618-4a59-9ab3-6d79056679a4","name":"Recursion and Backtracking For Intermediate","slug":"recursion-and-backtracking-for-intermediate-330","type":0},{"id":"cf72e22f-afa8-49ce-a548-df6bde7beb9a","name":"Coin Change - Combinations - 2","slug":"coin-change-combinations-2","type":1}],"next":{"id":"64f942e5-1a07-4063-a911-e0d73cb26534","name":"Coin Change - Combinations - 2 MCQ","type":0,"slug":"coin-change-combinations-2-mcq"},"prev":{"id":"85cb64c1-c744-4edb-b179-c8713a103db3","name":"Coin Change - Combinations - 1 MCQ","type":0,"slug":"coin-change-combinations-1-mcq"}}}

Coin Change - Combinations - 2

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 combinations of the n coins (same coin can be used again any number of times) using which the amount "amt" can be paid. Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

{"id":"7f434d28-aaf9-4bb1-9bbd-859b8924f620","name":"Coin Change - Combinations - 2","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 combinations of the n coins (same coin can be used \r\n again any number of times) using which the amount \"amt\" can be paid.\r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number amt","outputFormat":"Check the sample output and question video","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 <bits/stdc++.h>\nusing namespace std;\n void coinChange(int i, vector<int>&coins, int amtsf, int tamt, string asf) \n {\n // write your code here\n if (i == coins.size()) {\n if (amtsf == tamt) {\n cout<<asf<<\".\"<<endl;\n }\n return;\n }\n \n for (int j = tamt / coins[i]; j > 0; j--) {\n string pasf = \"\";\n for(int k = 0; k < j; k++){\n pasf += to_string(coins[i]) + \"-\";\n }\n coinChange(i + 1, coins, amtsf + coins[i]* j, tamt, asf+pasf+\"\");\n }\n coinChange(i + 1, coins, amtsf, tamt, asf);\n \n }\n int main()\n {\n int n;\n cin>>n;\n vector<int> coins(n);\n for(int i=0;i<n;i++)\n {\n cin>>coins[i];\n }\n int amt;\n cin>>amt;\n string ans=\"\";\n coinChange(0, coins, 0, amt, ans);\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void coinChange(int i, int[] coins, int amtsf, int tamt, String asf) {\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] coins = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n coins[i] = Integer.parseInt(br.readLine());\r\n }\r\n int amt = Integer.parseInt(br.readLine());\r\n coinChange(0, coins, 0, amt, \"\");\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n2\r\n3\r\n5\r\n6\r\n7\r\n12","sampleOutput":"2-2-2-2-2-2-.\r\n2-2-2-3-3-.\r\n2-2-2-6-.\r\n2-2-3-5-.\r\n2-3-7-.\r\n2-5-5-.\r\n3-3-3-3-.\r\n3-3-6-.\r\n5-7-.\r\n6-6-.","questionVideo":"https://www.youtube.com/embed/onUoUZDtak8?end=242","hints":[],"associated":[],"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":"082986ae-d618-4a59-9ab3-6d79056679a4","name":"Recursion and Backtracking For Intermediate","slug":"recursion-and-backtracking-for-intermediate-330","type":0},{"id":"cf72e22f-afa8-49ce-a548-df6bde7beb9a","name":"Coin Change - Combinations - 2","slug":"coin-change-combinations-2","type":1}],"next":{"id":"64f942e5-1a07-4063-a911-e0d73cb26534","name":"Coin Change - Combinations - 2 MCQ","type":0,"slug":"coin-change-combinations-2-mcq"},"prev":{"id":"85cb64c1-c744-4edb-b179-c8713a103db3","name":"Coin Change - Combinations - 1 MCQ","type":0,"slug":"coin-change-combinations-1-mcq"}}}
plane

Editor

Loading...

Coin Change - Combinations - 2

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 combinations of the n coins (same coin can be used again any number of times) using which the amount "amt" can be paid. Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

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

Check the sample output and question video

Example

Sample Input

5 2 3 5 6 7 12

Sample Output

2-2-2-2-2-2-. 2-2-2-3-3-. 2-2-2-6-. 2-2-3-5-. 2-3-7-. 2-5-5-. 3-3-3-3-. 3-3-6-. 5-7-. 6-6-.

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode