题目描述

这里有$n$列火车将要进站再出站，但是，每列火车只有1节，那就是车头。

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

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

车站示意如图：

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

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

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

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

数据范围
$1 \le n \le 20$

样例

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

搜索+模拟栈

这道题目数据范围明显就是搜索,再加上只需要输出二十种方案,我们完全可以搜索序列,顺便栈模拟一下即可,难度不高,直接上代码.

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int st[30],n,size;
vector<int>ans;
void dfs(int top,int x)
{
    if(size>=20)
        return ;
    if(x>n && top==0)
    {
        size++;
        for(int i=0;i<ans.size();i++)
            cout<<ans[i];
        puts("");
        return ;
    }
    if(top)
    {
        int now=st[top];
        ans.push_back(st[top]);
        dfs(top-1,x);
        ans.pop_back();
        st[top]=now;
    }
    if(x<=n)
    {
        st[top+1]=x;
        dfs(top+1,x+1);
    }
}
int main()
{   
    cin>>n;
    dfs(0,1);
    return 0;
}