题解 | 火车进站

回溯法

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

vector<vector<int>> out_order;
vector<int> path;

void backTrack(int index, vector<int>& order, stack<int>& st) {
    if(path.size() == order.size() && st.empty()) {
        out_order.push_back(path);
        return ;
    }

    //将当前火车入站
    if(index < order.size()) {
        st.push(order[index]);
        backTrack(index + 1, order, st);
        st.pop();
    }

    //将栈顶火车出站
    if(!st.empty()) {
        int train = st.top();
        st.pop();
        path.push_back(train);
        backTrack(index, order, st);
        st.push(train);
        path.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    stack<int> st;
    vector<int> order(n);
    for (int i = 0; i < n; ++i) {
        cin >> order[i];
    }
    out_order.clear();
    path.clear();
    backTrack(0, order, st);
    sort(out_order.begin(), out_order.end());
    for (auto& o : out_order) {
        for (int& i : o) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}