题解 | #火车进站#

解法：DFS+栈+SET
DFS用于找所有可能的情况，栈用于模拟火车进出，set用于保存结果并自动排序。
在DFS中的每一步只有两种可能：
①火车出站，即从栈顶弹出一个，保存在输出数组中
②新火车进站，从输入列表中取一个火车压入栈，因此需要一个index来指示当前取到第几个火车了

DFS终止条件为当前输出数组的size等于n，随即将输出数组保存在set中并return。
具体实现如下

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


void dfs(set<vector<int>>& outputse, vector<int>& invec, stack<int> ist, vector<int> otvec, int index, int& n) {
    if (otvec.size() == n) {
        outputse.insert(otvec);
        return;
    }
    //每一步要不从栈中弹一个出栈，要么从输入invec中压入一个车入栈
    for (int j = 0; j < 2; j++) {
        if (j == 0 && !ist.empty()) {//出栈要保证当前栈不为空
            int temp = ist.top();
            ist.pop();
            otvec.push_back(temp);
            dfs(outputse, invec, ist, otvec, index, n);
            ist.push(temp);
            otvec.pop_back();


        }
        else if (j == 1 && index < n ) {//入栈保证索引没有超出范围
            int temp = invec[index];
            ist.push(temp);
            index++;
            dfs(outputse, invec, ist, otvec, index, n);
            index--;
            ist.pop();
        }
    }
}


int main() {
    int n;
    while (cin >> n) {
        vector<int> invec(n, 0);
        for (int i = 0; i < n; i++) {
            cin >> invec[i];

        }
        set<vector<int>> outputse;
        stack<int> ist;
        ist.push(invec[0]);//初始默认将第一辆车压入栈，因此下面函数 的index默认从1开始
        vector<int> ovec;
        dfs(outputse, invec, ist, ovec, 1, n);
        for (auto& ele : outputse) {
            for (auto& i : ele) {
                cout << i << " ";
            }
            cout << endl;
        }
    }
}