题解 | 火车进站

#include <iostream>
#include <bits/stdc++.h>
#include <string>
using namespace std;
//70
vector<int> nums;
vector<string> res;
int n;

void func(int idx, string temp, vector<int> myStack) {
    if (idx == n) {
        //火车已经入站完毕，将站台清空即可
        while (!myStack.empty()) {
            temp = temp + to_string(myStack.back()) + ' ';
            myStack.pop_back();
        }
        temp.pop_back();
        res.emplace_back(temp);
    } else {
        //火车还未入站完毕，下一辆入站的火车是nums[idx]
        //若火车站不为空，可以选择出栈，并进入下一层
        //可以选择入站，并进入下一层
        if (!myStack.empty()) {
            int tt = myStack.back();
            myStack.pop_back();
            func(idx, temp + to_string(tt) + ' ', myStack);
            myStack.push_back(tt);
        }
        myStack.push_back(nums[idx]);
        func(idx + 1, temp, myStack);
    }
}

int main() {
    cin >> n;
    nums = vector<int>(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    vector<int> myStack;
    func(0, "", myStack);
    sort(res.begin(), res.end());
    for (string& s : res)
        cout << s << '\n';
    return 0;
}
// 64 位输出请用 printf("%lld")