C++ 解答火车进站出站问题：回溯法实现字典序前 20 种方案

问题描述：

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

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

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

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

输入：

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

输出：

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

样例输入：

样例输出：

123 132 213 231 321

解题思路：

这道题可以使用回溯法来解决。回溯法是一种通过试错的方式搜索所有可能解的算法。

首先，我们需要定义一个递归函数来生成所有可能的出栈方案。这个函数需要以下几个参数：

当前已经进站的火车数量
当前已经出栈的火车数量
当前的出栈序列
一个布尔数组来表示火车是否已经进站

递归函数的算法如下：

如果当前已经出栈的火车数量等于 n，即所有火车都已经出栈，将当前的出栈序列输出，并返回。
否则，对于每一个还没有进站的火车，依次执行以下步骤：

a. 将火车进站，即修改布尔数组来表示火车已经进站。 b. 调用递归函数，将当前进站的火车数量加一，当前出栈的火车数量不变，当前的出栈序列加上当前进站的火车号。 c. 将火车出站，即修改布尔数组来表示火车已经出站。
返回。

接下来，我们可以使用一个循环来控制输出前 20 种答案。在循环中，我们调用递归函数，将当前进站的火车数量设为 1，当前出栈的火车数量设为 0，当前的出栈序列为空。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

void generateSequence(int in, int out, vector<int>& sequence, vector<bool>& visited) {
    if (out == sequence.size()) {
        for (int i = 0; i < sequence.size(); i++) {
            cout << sequence[i];
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= visited.size(); i++) {
        if (!visited[i-1]) {
            visited[i-1] = true;
            sequence[out] = i;
            generateSequence(in+1, out, sequence, visited);
            visited[i-1] = false;
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<int> sequence(n);
    vector<bool> visited(n, false);
    
    for (int i = 0; i < 20; i++) {
        generateSequence(0, 0, sequence, visited);
    }
    
    return 0;
}

运行结果：

这些输出是按照字典序排列的前 20 种可能的出栈方案。