题解 | #火车进站#

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

class solution {
  public:
    //回溯(全排列的思路)+栈(模拟出入栈)
    int n;
    vector<int> car;
    vector<int> order;
    vector<int> path;
    vector<bool> used;
    vector<vector<int>> res;

    bool check(vector<int>& path) {
        stack<int> st;
        int j = 0;
        for (int i = 0; i < n; i++) {
            st.push(order[i]);
            while (!st.empty() && path[j] == st.top() &&
                    j < n) { //放入直到栈顶等于path[j]，然后弹出
                st.pop();
                j++;
            }
        }
        return st.empty();
    }

    void backtracking(vector<bool>& used) {
        if (path.size() == n) {
            if (check(path)) {
                res.push_back(path);
            }
            return;
        }
        for (int i = 0; i < car.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(car[i]);
            backtracking(used);
            path.pop_back();
            used[i] = false;
        }
    }
    solution(int n,vector<int>& c,vector<bool>& u,vector<int>& o):n(n),car(c),used(u),order(o){}
};
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<int> car;
        int tmp;
        for (int i = 0; i < n; i++) {
            cin >> tmp;
            car.push_back(tmp);
        }
        vector<int> order(car);
        sort(car.begin(), car.end());
        vector<bool> used(n, false);
        solution s(n,car,used,order);
        s.backtracking(used);
        
        for(auto & re : s.res){
            for(int j = 0; j<n; j++){
                cout << re[j] << " ";
            }
            cout<<endl;
        }
    }
    return 0;
}