题目描述

题目描述
这里有nn列火车将要进站再出站，但是，每列火车只有1节，那就是车头。

这nn列火车按11到nn的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。

也就是说这个火车站其实就相当于一个栈，每次可以让右侧头火车进栈，或者让栈顶火车出站。

车站示意如图：

    出站<——    <——进站
             |车|
             |站|
             |__|

现在请你按《字典序》输出前20种可能的出栈方案。

输入格式
输入一个整数nn，代表火车数量。

输出格式
按照《字典序》输出前20种答案，每行一种，不要空格。

数据范围
1≤n≤201≤n≤20

此题直接暴搜，题目中有两种操作，要么进站要么出站，出站的一系列火车比作一个数组，车站可以比作一个栈，进站的数用一个变量代替即可；
注意：由于是按照字典序的顺序输出，故出站操作一定要在进站操作之前，才能保证出站的数始终比进站的数小，借用Yxc大佬代码

样例

输入样例：
3
输出样例：
123
132
213
231
321

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
vector<int> state1;
stack<int> state2;
int state3=1,n,cnt=20;
void dfs()
{
   if(!cnt) return;//只需要输出前20种即可
   if(state1.size()==n)//达到临界值
   {
       cnt--;
       for(auto x:state1) cout<<x;
       cout<<endl;
       return;
   }
   if(state3<=n)
   {
       state2.push(state3);//出站操作
       state3++;
       dfs();
       state2.pop();//恢复到出站操作之前
       state3--;
   }
     if(state2.size())
   {
       state1.push_back(state2.top());//入站操作
       state2.pop();
       dfs();
       state2.push(state1.back());//恢复到进站操作之前
       state1.pop_back();
   }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    dfs();
    return 0;
}