题解 | #火车进站#

#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<vector<int>> res;
void backtrack(int N, vector<int>& inSeq, vector<int>& outSeq, stack<int>& station, int index){
    if(outSeq.size() == N){
        res.push_back(outSeq);
        return;
    }
    //入
    if (index < N) {
        int inTrain = inSeq[index];
        station.push(inTrain);
        backtrack(N, inSeq, outSeq, station, index + 1);
        station.pop();
    }

    //出
    if(!station.empty()){
        int top = station.top();
        outSeq.push_back(top);
        station.pop();
        backtrack(N, inSeq, outSeq, station, index);
        station.push(top);
        outSeq.pop_back();
    }
}
int main() {
    int n;
    cin >> n;
    int x;
    vector<int> inSeq;
    vector<int> outSeq;
    stack<int> station;
    while(cin >> x){
        inSeq.push_back(x);
    }
    backtrack(n, inSeq, outSeq, station, 0);
    sort(res.begin(), res.end());
    for(auto &i : res){
        for(auto &j : i){
            cout << j << " ";
        }
        cout << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")