进出栈序列问题 CH101（递归）

背景

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

描述

有n列火车按1到n的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。
（某生：不就是个栈吗？每次可以让右侧头火车进栈，或者让栈顶火车出站？
老师：闭嘴！）
就像这样：
出站<——-    <——进站
|车|
|站|
|__|
现在请你按《字典序》输出前20种可能的出栈方案。

 

输入格式

一个整数 n<=20

输出格式

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

样例输入

3

样例输出

123
132
213
231
321

• 题解：
  • 暴力递归：
    1. 如果栈非空，把当前栈顶的数出栈
    2. 把下一个数进栈

这里需要注意递归的顺序问题，而且我们将每次进入递归函数定义为第x个数进栈，所以操作1不需要将x+1再进行递归，而操作2需要。

代码：

//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
const int MAXN = 50010; 
int n,m=0,cnt=0,top=0;
int a[21],c[21];
void dfs(int x){//当第x个数入栈时 
	if(m==20)return ;//题目中要求最多输出20个输出
	if(x>n+1)return ;//第n+1次进入时不是终止条件，因为第n+1个数进栈时可能进行输出
	if(cnt==n){
		rep(i,1,n){
			cout<<c[i];
		}
		cout<<endl;
		m++;
	}
	if(top){//把这个条件摆在前面是因为多次尝试后，与前面的终止条件配套的顺序是这样，类似于二分，有配套的写法
		int tmp=a[top--];
		c[++cnt]=tmp;
		dfs(x);
		cnt--;
		a[++top]=tmp;
	}
	a[++top]=x;
	dfs(x+1);
	top--;
	
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}