ZeroJudge A524: 手機之謎

題目敘述

本題採EOF方式收資料，每筆資料只有一個正整數N，要求輸出所有從1到N長度為N的字串，由大輸出到小。

範例輸入 #1

3

2

範例輸出 #1

321

312

231

213

132

123

21

12

解題思路

使用遞迴將每一種數字加到字串中，需要注意的是不能有重複的數字，可以使用Map或Set來做判斷。當判斷到字串長度為N時，將字串轉為整數並存到一個陣列中，一樣要先判斷是否已經有存過一樣的數字了。最後使用Sort排序陣列之後從最後一項往前輸出即可。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int N;
vector<int>ans;
map<int, int>MAP;

void hi(string str, map<int, int>exist)
{
    if (str.length() == N)
    {
        int tmp;
        if (str.length() == 1) tmp = int(str[0] - '0');
        else tmp = stoi(str);
        if (MAP[tmp] == 0)
        {
            ans.push_back(tmp);
            MAP[tmp]++;
            return;
        }
    }
    for (int i = 1; i<=N; i++)
    {
        if (exist[i] == 0)
        {
            exist[i]++;
            hi(str+to_string(i), exist);
            exist[i]--;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N)
    {
        string str = "";
        map<int, int>h;
        hi(str, h);
        sort(ans.begin(), ans.end());
        for (int i = int(ans.size())-1; i>=0; i--)
        {
            cout << ans[i] << "\n";
        }
        ans.clear();
        MAP.clear();
    }
}