• dfs爆搜，注意20剪枝
• 所有火车都进栈出栈这代表一个结果产生
• 车站不为空就能选择出栈
• 如果还有火车未进栈，则可以选择进栈

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

using namespace std;

int n;  // 火车数量
vector<string> result;  // 存储所有可能的出栈顺序
stack<int> station;  // 模拟车站栈
vector<int> current;  // 当前出栈的火车顺序

// 深度优先搜索函数
void dfs(int inStack) {
    // 如果已经找到20种方案，停止搜索
    if (result.size() >= 20) {
        return;
    }

    // 如果所有火车都已进栈且栈为空，表示所有火车都已出栈
    if (inStack == n && station.empty()) {
        string s;
        // 将当前出栈顺序转换为字符串
        for (int v : current) {
            s += to_string(v);
        }
        // 将结果加入结果集
        result.push_back(s);
        return;
    }

    // 如果栈不为空，进行出栈操作
    if (!station.empty()) {
        int top = station.top();  // 获取栈顶元素
        station.pop();  // 出栈
        current.push_back(top);  // 将出栈的火车加入当前出栈顺序
        dfs(inStack);  // 递归调用dfs
        current.pop_back();  // 回溯，移除最后一个出栈的火车
        station.push(top);  // 将出栈的火车重新入栈
    }

    // 如果还有火车未进栈，进行进栈操作
    if (inStack < n) {
        station.push(inStack + 1);  // 将下一列火车进栈
        dfs(inStack + 1);  // 递归调用dfs
        station.pop();  // 回溯，移除最后一个进栈的火车
    }
}

int main() {
    cin >> n;  // 读取火车数量
    dfs(0);  // 调用dfs函数开始搜索

    // 输出前20种方案
    for (int i = 0; i < result.size() && i < 20; i++) {
        cout << result[i] << endl;
    }

    return 0;
}