题解 | #火车进站#

#include <iostream>
#include <bits/stdc++.h>
// 后进先出，考虑栈
// 通过回溯对情况进行遍历，利用栈来维护车站内列车的序列
using namespace std;
// 考虑出栈的时机不同
vector<vector<int>>results;
void backtracking(stack<int>inStation,vector<int>path,vector<int>seque,int num,int pos){
    if(path.size() == num){results.emplace_back(path);return ;}
    if(inStation.empty()){
        inStation.push(seque[pos]);
        backtracking(inStation,path, seque,num, pos+1);
    }
    else {
        // 出一辆车的情况
        path.emplace_back(inStation.top());
        inStation.pop();
        backtracking(inStation,path, seque,num, pos);
        // 依旧进一辆车的情况
        if(pos < num)
        {
            inStation.push(path.back());
            path.erase(path.end()-1);
            inStation.push(seque[pos]);
            backtracking(inStation,path, seque,num, pos+1);
        }
    }

}
int main() {
    int num;cin >> num;
    vector<int>seque(num,0);
    for(int i = 0;i<num;++i){
        cin >> seque[i];
    }
    // 递归解决
    vector<int>path;
    stack<int>inStation;
    backtracking(inStation,path, seque,num, 0);
    sort(results.begin(),results.end());
    for(int i = 0;i<results.size();++i)
    {
        for(int j = 0;j<results[i].size();j++)
        {
            cout << results[i][j] << ' ';
        }
        cout << endl;
    }

}
// 64 位输出请用 printf("%lld")