题目链接

算法竞赛进阶指南-43.火车进栈

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

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

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

车站示意如图：

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

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

输入格式

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

输出格式

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

数据范围

$1 \le n \le 20$

输入样例：

3

输出样例：

123
132
213
231
321

Method : 栈 + 递归

很显然，对于任一个状态，只有两个选择：

1. 把下一个数入栈；
2. 把当前栈顶的数出栈（如果当前栈非空）。

这就对应了递归的两个分支，因此可以用递归来枚举所有可能的方案。

此外，因为要按字典序输出，所以出栈的分支必须放在入栈的分支前面

#include <stack>
#include <vector>
#include <iostream>

using namespace std;

int n;
int remain = 20;

vector<int> path;
stack<int> stk;

void dfs(int u, int n) {
    if (!remain) return;
    if (u - 1 > n) {
        if (path.size() == n) {
            remain --;
            for (int i = 0; i < path.size(); i ++) {
            printf("%d", path[i]);
            }
            puts("");
        }
        return;
    }

    if(!stk.empty()) {
        path.push_back(stk.top());
        stk.pop();
        dfs(u, n);
        // 回溯
        stk.push(path.back());
        path.pop_back();
    }
    
    stk.push(u);
    dfs(u + 1, n);
    // 回溯
    stk.pop();
}

int main() {
    cin >> n;
    
    dfs(1, n);
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(2^n)}$， 递归每次产生两次分支，一共递归n次，remain作为剪枝。

• 空间复杂度：${O(n)}$。