题解 | #火车进站#

#include <iostream>
#include <stack>
#include <vector>
#include <map>
using namespace std;
int n;
int a[10];
vector<int> state1; //出站火车状态表示
stack<int> state2;  //在站中的火车
int state3 = 1;     //还未进站的火车，当前枚举到第几辆车
map<string, int> mp;    //存储最后结果，自动排序

void dfs()
{
    if(state1.size() == n)
    {
        string res;
        for(auto t : state1) 
        {   
            res += t + '0';
            res += ' ';
        }
        mp[res] = 1;
        return;
    }
    //在车站中栈顶火车只两种选择：一个是出栈一个是不出栈，不出栈也就是右边火车进栈
    if(state2.size())   
    {
        state1.push_back(state2.top());
        state2.pop();
        dfs();
        state2.push(state1.back());//恢复现场
        state1.pop_back();
    }
    if(state3 <= n)
    {
        state2.push(a[state3 ++] );
        dfs();
        state2.pop();
        state3 --;
    }

}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    dfs();
    for(auto t : mp) cout << t.first << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")