Input different denominations of coins, and then input an amount. Then, list out all possible ways to make change. For example, if there are 3 types of coin denominations: $1, $5, and $10, and you want to make $17 in change, if we represent the change methods as "(number of $1 coins, number of $5 coins, number of $10 coins)," there will be several possible methods:
- (2,1,1)
- (2,3,0)
- (7,0,1)
- (7,2,0)
- (12,1,0)
- (17,0,0)
The rule for ordering: For example, (7,0,1) comes before (12,1,0) because 7 is smaller than 12. When comparing (7,0,1) and (7,2,0), since the first number, 7, is equal in both, we compare the second number. Since 0 is smaller than 2, (7,0,1) comes before (7,2,0).
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input has 3 lines. The first line contains a number, N, representing the number of different denominations of coins (N <= 5). The second line consists of N integers, representing the N denominations of coins. The third line contains a single integer representing the amount for which change is required. The denominations of the coins and the amount are both positive integers not exceeding 100. | List out each change-making method, enclosing the quantity of each coin in parentheses, separated by commas. Followed by a line break after each method. The order of different change-making methods should follow the rules given in the problem statement. |
| 3 1 5 10 17 | (2,1,1) (2,3,0) (7,0,1) (7,2,0) (12,1,0) (17,0,0) |
Thought Process
Use a function to increment each coin value and check if it equals the required amount. If it does, first store the combination of coins in a two-dimensional array. Next, directly sort this two-dimensional array. It's important to check whether the combination of coins has already been stored in the array when storing it, which can be done using a Map or Set.
Sample Code－ZeroJudge B511: Changing Coins
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int N, target;
map<int, int>MAP;
vector<vector<int>>ans;
map<vector<int>, int>mm;
void hi(vector<int>num, int sum)
{
if (sum == target)
{
if (mm[num] == 0)
{
ans.push_back(num);
mm[num]++;
}
return;
}
else if (sum > target) return;
for (int i = 0; i<N; i++)
{
if (sum + MAP[i] <= target)
{
num[i]++;
hi(num, sum+MAP[i]);
num[i]--;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N;
vector<int>v;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
MAP[i] = tmp;
v.push_back(0);
}
cin >> target;
hi(v, 0);
sort(ans.begin(), ans.end());
for (int i = 0; i<ans.size(); i++)
{
cout << "(" << ans[i][0];
for (int j = 1; j<ans[i].size(); j++)
{
cout << "," << ans[i][j];
}
cout << ")\n";
}
}
//ZeroJudge B511
//Dr. SeanXD