题解 | #火车进站#

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(vector<int>& in, int index, stack<int>& st, vector<int>& out,
         vector<vector<int>>& res) {
    if (index >= in.size() && st.empty()) {
        // 已完成全部入栈和出栈工作
        res.push_back(out);
        return;
    }
    if (index < in.size()) {
        // 入栈
        st.push(in[index]);
        // 递归下一步是入栈海事出栈
        dfs(in, index + 1, st, out, res);
        // 返回状态
        st.pop();
    }
    if (!st.empty()) {
        // 出栈
        out.push_back(st.top());
        st.pop();
        dfs(in, index, st, out, res);
        st.push(out.back());
        out.pop_back();
    }
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> arr(n, 0);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }
        stack<int> st;
        vector<int> out;
        vector<vector<int>> res;
        dfs(arr, 0, st, out, res);
        sort(res.begin(), res.end());
        for (auto r : res) {
            for (auto item : r) {
                cout << item << " ";
            }
            cout << endl;
        }
    }

    return 0;
}