ZeroJudge E942: 數字排列

給予 N 個相異的正整數，請按大小順序輸出所有可能的排列組合。

範例測資

範例輸入範例輸出
第一行有一個正整數 N (1 ≤ N ≤ 9），代表有幾個相異的正整數。
第二行則有 N 個相異的正整數 x（0 ≤ x ≤ 4,294,967,295）。		按照大小順序，輸出所有可能的排列組合。
4
30 10 20 40		10 20 30 40
10 20 40 30
10 30 20 40
10 30 40 20
10 40 20 30
10 40 30 20
20 10 30 40
20 10 40 30
20 30 10 40
20 30 40 10
20 40 10 30
20 40 30 10
30 10 20 40
30 10 40 20
30 20 10 40
30 20 40 10
30 40 10 20
30 40 20 10
40 10 20 30
40 10 30 20
40 20 10 30
40 20 30 10
40 30 10 20
40 30 20 10
ZeroJudge E942 範例測資

解題思路

收完資料之後可以先進行一次排序，記得使用 Long Long Int。然後可以跑一個 DFS，並且宣告一個 Map 來存目前加過哪些數字、還有一個 Vector 來存目前加的數字。

如果 Vector.size() == N 就可以將目前的 Vector 存到一個二維陣列中，這個二維陣列為答案。否則就跑一個 For迴圈 從 0 到 N-1，如果目前的數字在 Map 中沒有紀錄，就再互叫一次 DFS，只是這次將 Map[數字]++，並且將 Vector.push_back(數字)。呼叫完之後記得要將 Map[數字]– 和 Vector.pop_back()。

最後輸出二維陣列中的資料。

範例程式碼－ZeroJudge E942: 數字排列

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

int N;
vector<long long int>num;
vector<vector<long long int>>ans;

void DFS(vector<long long int>v, map<long long int, int>MAP) {
    if (v.size() == N) {
        ans.push_back(v);
        return;
    }
    for (int i = 0; i<N; i++) {
        if (MAP[num[i]] == 0) {
            MAP[num[i]]++;
            v.push_back(num[i]);
            DFS(v, MAP);
            v.pop_back();
            MAP[num[i]]--;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++) {
        long long int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    map<long long int, int>MAP;
    vector<long long int>v;
    DFS(v, MAP);
    for (auto & an : ans) {
        for (int j = 0; j<N; j++) {
            cout << an[j] << " ";
        }
        cout << "\n";
    }
}

//ZeroJudge E942
//Dr. SeanXD
標籤

相關文章

發佈留言