ZeroJudge I646: 排列組合-排列

高中數學有教到排列組合，有時候會將所有的「排列」方法列出來。現在就麻煩你幫老師做這一件事吧！

範例測資

範例輸入範例輸出
輸入含有多筆測資，每筆測資一列，含有1個正整數 N (1 <= N <= 7) 代表有多少個東西要排列。N 件東西的代號以 a、b、c、… 代表。
當 N = 0 時代表輸入結束 (這筆不用輸出)。		對每筆測資輸出所有的排列，每個排列一列，不同的排列方式按字典順序輸出。
2
3
0		ab
ba
abc
acb
bac
bca
cab
cba

解題思路

使用 DFS 並使用字串的方式將答案加出來，跑一個 For迴圈 並宣個一個 Map 來存目前以經存放過的字母，如果目前跑到的字母沒有被放過就將 Map[字母]++ 和 字串+字母 並再一次呼叫 DFS，呼叫完記得要將 Map 還有字串復原。

範例程式碼－ZeroJudge I646: 排列組合-排列

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

vector<string>ans;
int N;

void DFS(string str, map<char, int>MAP) {
    if (str.length() == N) {
        ans.push_back(str);
        return;
    }
    for (int i = 0; i<N; i++) {
        char ch = i + 'a';
        if (MAP[ch] == 0) {
            MAP[ch]++;
            DFS(str+ch, MAP);
            MAP[ch]--;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N && N != 0) {
        ans.clear();
        map<char, int>MAP;
        DFS("", MAP);
        for (int i = 0; i<ans.size(); i++) {
            cout << ans[i] << "\n";
        }
    }
}

//ZeroJudge I646
//Dr. SeanXD
標籤

相關文章

發佈留言