题解 | #火车进站#

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

vector<vector<int>> result;
vector<int> temp;

void dfs(stack<int>& st,vector<int>& table,int start){
    if(st.empty()&&start==table.size()){
        result.push_back(temp);
        return;
    }
    if(start<table.size()){
        st.push(table[start]);
        dfs(st,table,start+1);
        st.pop();
    }
    if(!st.empty()){
        temp.push_back(st.top());
        st.pop();
        dfs(st,table,start);
        st.push(temp.back());
        temp.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> table(n);
    for(int i=0;i<n;++i)
        cin >> table[i];
    stack<int> st;
    dfs(st,table,0);
    sort(result.begin(), result.end());
    /*for(auto p:result){
        for(int x:p)
            cout << x << ' ';
        cout << endl;
    }*/
    for(int i=0;i<result.size();++i){
        for(int j=0;j<result[i].size();++j)
            cout << result[i][j] << ' ';
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")