輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。譬如有 3 種銅板面值分別是 1 元、5 元、10 元，假設要湊出 17 元，如果把找零方法表示成 「(1 元個數,5 元個數,10 元個數)」，總共會有下列幾種方法：
- (2,1,1)
- (2,3,0)
- (7,0,1)
- (7,2,0)
- (12,1,0)
- (17,0,0)
排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目 7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入有三行 第一行一個數字 N 代表有幾種不同面值的銅板 (N <= 5) 第二行就是 N 個整數，表示 N 種對應的銅板面值 第三行一個數字是要需要找零的金額 銅板面值和金額都是不超過100的正整數。 | 列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。不同的找零方法的排列順序要依照題目的規定。 |
| 3 1 5 10 17 | (2,1,1) (2,3,0) (7,0,1) (7,2,0) (12,1,0) (17,0,0) |
解題思路
使用函式將每個幣值都加加看，如果等於要求的數量的話先將幣種組合存到一個二維陣列中，接下來直接 Sort 這個二維陣列，需要注意的是存幣種組合的時候要判斷這個幣種組合是否已經有存到陣列中了，可以使用 Map 或 Set 來判斷。
範例程式碼－ZeroJudge B511: 換銅板
#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