题解 | #HJ77 火车进站#

#include <bits/stdc++.h>
using namespace std;
vector<int> temp;
vector<int> in, out ,in_copy;
stack<int> st;
vector<int> visited(11, 0);
bool check(vector<int>& out) {//检查改出栈顺序是否可能
    while (!st.empty()) st.pop();
    int index = 0;
    for (int i = 0; i < in.size(); i++) {
        st.push(in[i]);
        while (!st.empty() && st.top() == out[index]) {
            index++;
            st.pop();
        }
    }
    return st.empty();
}
void choose(int n, int index) {
    if (index == n) {
        if (check(temp)) {
            for (int i = 0; i < temp.size(); i++) {
                if (i != 0) cout << " ";
                cout << temp[i];
            }
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < n; i++) {//按从小到大 生成全排列
        if (visited[in_copy[i]] == 0) {
            temp.push_back(in_copy[i]);
            visited[in_copy[i]] = 1;
            choose(n, index + 1);
            temp.pop_back();
            visited[in_copy[i]] = 0;
        }
    }
}
int main() {
    int n;
    cin >> n;
    in.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> in[i];
        in_copy.push_back(in[i]);
    }
    sort(in_copy.begin(),in_copy.end()); //枚举全排列
    choose(n, 0);
    return 0;
}