题解 | #火车进站 回溯#

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

int n;
vector<int> nums;
stack<int> st;
vector<vector<int>> res;

void dfs(int curr, vector<int>& ans){
    if(curr == n && st.empty()){
        res.push_back(ans);
        return;
    }
    
    if(curr < n){
        st.push(nums[curr]);
        dfs(curr+1, ans);
        st.pop();
    }
    
    if(st.size()){
        int tmp = st.top();
        ans.push_back(tmp);
        st.pop();
        dfs(curr, ans);
        st.push(tmp);
        ans.pop_back();
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        nums.push_back(x);
    }
    
    vector<int> ans;
    dfs(0, ans);
    
    sort(res.begin(), res.end());
    
    for(int i = 0; i < res.size(); i++){
        for(int j=0; j<res[i].size(); j++){
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}