题解 | 火车进站

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

void dfs(const vector<int>& nums, int index, stack <int>& st, vector<int>& out,
         vector<vector<int>>& res) {
    //栈为空，全部进站并且全部出栈，可以返回至调用层函数
    if (index >= nums.size() && st.empty()) {
        res.push_back(out);
        return;
    }
    //进栈。当未全部进栈时可以进栈。进栈后再出栈
    if (index < nums.size()) {
        st.push(nums[index]);
        dfs(nums, index + 1, st, out, res);
        st.pop();
    }
    //出栈。当栈非空时可以出栈，
    //出栈后是一种可能，进行递归，
    //出栈后再进栈，相当于不出栈，也是一种可能。继续进栈（在上一层调用的函数中进行进栈），进行递归
    if (!st.empty()) {
        out.push_back(st.top());
        st.pop();
        dfs(nums, index, st, out, res);
        st.push(out.back());
        out.pop_back();
    }
}
int main() {
    int n;
    vector<vector<int>>res;
    stack <int>st;
    vector<int>out;
    while (cin >> n) {
        vector<int>nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        dfs(nums, 0, st, out, res);
        sort(res.begin(), res.end());
        for (auto& re : res) {
            for (auto& p : re) {
                cout << p << " ";
            }
            cout << endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")