题解 | #火车进站#

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int x, y, z;
void recursion(const vector<int>& in, int index, stack<int> st, vector<int> out, vector<vector<int>>& res, bool dopush)
{
    if(st.empty() && out.size()==in.size()) {
        if(dopush) return;
        res.push_back(out);
        // out.clear();
        return;
    }
    if(dopush) {
        if(index >= in.size()) return;
        st.push(in[index]);
        index++;
    } else {
        if(st.empty()) return;
        y = st.top();
        st.pop();
        out.push_back(y);
    }
    recursion(in, index, st, out, res, false);
    recursion(in, index, st, out, res, true);
}

int main()
{
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) { cin >> nums[i]; }
        stack<int> st;
        vector<int> path;
        vector<vector<int>> res;
        recursion(nums, 0, st, path, res, true);
        sort(res.begin(), res.end());
        for (auto p : res) {
            for (int a : p) { cout << a << " "; }
            cout << endl;
        }
    }
    return 0;
}

深度优先遍历，出栈或者进栈，都是可选的呢，所以需要回溯的方式，因每个出栈或者进栈，都是一次选择，产生的出栈序列都不相同，所以不能用引用数组，不能用“引用”，需要直接传参，断开connect， 就可以恢复现场，回溯的。