都知道要写一个dfs去模拟栈，但实际上如何组织搜索的顺序，怎么定搜索的框架我一开始想了很久。
一开始的思路：对于当前的状态，要么输出，要么输出栈顶元素，然后入栈。这样的搜索框架显然是单调的，每一次都会加一层的深度，最终输出栈中剩余的所有的元素。
然而这是错误的，问题在于，输出栈顶元素与入栈不一定需要紧接着操作，亦即：我们的栈中有多个元素的时候，我们可以输出其中的若干，而非只输出第一个。
换而言之，我们的搜索框架实际上是可以在一层中停留的，这是因为当前处理到的元素$i$与当前栈中的元素数共同组成了搜索中的一个状态。
理解了这一点，搜索的大致框架就可以写出来。代码中还有一些需要注意的细节，比如保留现场，比如自己要自己去写一个栈（否则无法输出）。

算法

模拟+dfs

搜索框架：
边界：当前处理的元素$i$大于元素总数，此时输出答案队列$q$中的所有元素，若栈中还有元素，则全部输出。
一般：由于需要按照字典序输出，故而优先考虑输出当前栈顶的元素（如果当前栈中没有元素，则跳过），其次考虑将当前的元素放入栈中。

时间复杂度

深搜，指数级。

参考文献

lyd书中给出了搜索的思路（一开始走了弯路TAT）。

C++ 代码

#include <bits/stdc++.h>
#define oj 
using namespace std;

int s[1000000];
int top;//栈顶
int cnt;//记录当前输出的方案数量
int n;
vector<int> q;//答案序列
bool dfs(int cur)//技巧：返回值为布尔类型，调用时判断，为真则结束调用
{
    if (cur == n + 1)//边界
    {
        cnt++;
        if (cnt > 20)
            return true;
        for (int i = 0; i < q.size(); i++)
        {
            printf("%d", q[i]);
        }
        for (int i=top; i>=0; i--) {
            printf("%d", s[i]);
        }
        printf("\n");
        return false;
    }
    else
    {
        if(top>=0){
            int tem = s[top];
            q.push_back(tem);
            top--;
            if(dfs(cur))return true;
            q.pop_back();
            s[++top]=tem;//恢复现场，十分重要
        }
        s[++top]=cur;
        if(dfs(cur + 1))return true;
        top--;
    }
    return false;
}

int main()
{
#ifndef oj
    freopen("data.in", "r", stdin);
    freopen("oj.out", "w", stdout);
#endif
    cin >> n;
    cnt = 0;
    top =- 1;//初始化
    dfs(1);//参数为当前处理到的元素
    return 0;
}