题解 | #火车进站#

递归写法：

• 新建一个栈stack<int>作为车站，每次只有两种操作：新车入栈、栈顶出栈，两种操作执行的前提分别是：还有车没入过站（id < N，v[id]是待入栈的元素）、栈不为空（!st.empty()）
• 递归边界就是当上述两个条件都不满足时（车已经全部入过站并且站里没有车了），递归结束，保存当前递归分支的出栈顺序，最后用sort对结果排序即可。
• 注意每进入一个分支之后，要恢复栈st和数组temp之前的状态。

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

stack<int> st;
vector<int> temp; // 出站序列
vector<int> v;    // 入站序列
int N;
vector<vector<int>> ans;// 存储结果

void dfs(int id)
{
    if (id == N && st.empty()) // 递归边界
    {
        ans.push_back(temp);
        return;
    }
    // 新车入站
    if (id < N)
    {
        st.push(v[id]);
        dfs(id + 1); // 进入分支
        st.pop();
    }
    // 栈顶出站
    if (!st.empty())
    {
        int n = st.top();
        temp.push_back(n);
        st.pop();
        dfs(id); // 进入分支
        st.push(n);
        temp.pop_back();
    }
}

int main() {
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];
    dfs(0);
    sort(ans.begin(), ans.end());
    // 输出
    for (auto plan : ans)
    {
        for (auto n : plan)
            cout << n << " ";
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")