题解 | 火车进站

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n;
vector<int> in_seq;               // 输入的入站序列
vector<vector<int>> results;      // 所有合法的出站序列

void backtrack(int in_index, stack<int>& st, vector<int>& out_seq) {
    if (out_seq.size() == n) {
        results.push_back(out_seq);
        return;
    }

    // 尝试入栈
    if (in_index < n) {
        st.push(in_seq[in_index]);
        backtrack(in_index + 1, st, out_seq);
        st.pop();  // 回溯
    }

    // 尝试出栈
    if (!st.empty()) {
        int top = st.top(); st.pop();
        out_seq.push_back(top);
        backtrack(in_index, st, out_seq);
        out_seq.pop_back();
        st.push(top);  // 回溯
    }
}

int main() {
    cin >> n;
    in_seq.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> in_seq[i];
    }

    stack<int> st;
    vector<int> out_seq;

    backtrack(0, st, out_seq);

    // 排序结果
    sort(results.begin(), results.end());

    // 输出结果
    for (const auto& seq : results) {
        for (int i = 0; i < seq.size(); ++i) {
            if (i > 0) cout << " ";
            cout << seq[i];
        }
        cout << "\n";
    }

    return 0;
}