ZeroJudge E942: Sorting Numbers

Given N different positive integers, please output all possible permutations in ascending order.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains a positive integer N (1 ≤ N ≤ 9), indicating how many distinct positive integers there are.
The second line contains N distinct positive integers x (0 ≤ x ≤ 4,294,967,295).		Output all possible permutations in ascending order.
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 Sample Test Case

Thought Process

After collecting the data, it's a good idea to perform a sorting operation, remembering to use a Long Long Int. Then you can run a DFS, and declare a Map to keep track of which numbers have been added, along with a Vector to store the currently added numbers.

If Vector.size() == N, you can store the current Vector in a two-dimensional array, which will be the answer. Otherwise, run a For loop from 0 to N-1, if the current number is not recorded in Map, call DFS again, but this time increment Map[number] and push_back the number into Vector. After the call, remember to decrement Map[number] and pop_back from Vector.

Finally, output the data in the two-dimensional array.

Sample Code－ZeroJudge E942: Sorting Numbers

#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
Tags

Related Posts

Comments