题解 | #火车进站#

#include <algorithm>
#include <iostream>
#include <random>
#include <stack>
#include <vector>
using namespace std;

vector<vector<int>> results;

void backtrack(vector<int>& in_seq, vector<int>& out_seq, int n, stack<int>& stk){
    if(out_seq.size() == n){
        results.push_back(out_seq);
        return;
    }
    
    if (!in_seq.empty()) {
        int in_train = in_seq[0];
        in_seq.erase(in_seq.begin());
        stk.push(in_train);
        backtrack(in_seq, out_seq, n, stk);
        stk.pop();
        in_seq.insert(in_seq.begin(), in_train);
    }
    if(!stk.empty()){
        int top_train = stk.top();
        out_seq.push_back(top_train);
        stk.pop();
        backtrack(in_seq, out_seq, n, stk);
        stk.push(top_train);
        out_seq.pop_back();
    }
}

int main() {
    int n;
    cin>>n;
    vector<int> in_seq(n);

    for (auto&seq:in_seq) {
        cin>>seq;
    }

    vector<int> out_seq;
    stack<int> stk;

    backtrack(in_seq, out_seq, n,stk);
    sort(results.begin(), results.end());
           
    for (auto& result:results) {
        for (int i=0; i<result.size()-1; i++) {
            cout<<result[i]<<" ";
        }
        cout << result[result.size()-1]<<endl;

    }

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