题解 | #火车进站#全排列+栈

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

bool checkValid(vector<int>& vec, vector<int>& candidate) {
    stack<int> stack;
    int i = 0, j = 0;
    while (j < candidate.size()) {
        while (!stack.empty() && stack.top() == candidate[j]) {
            stack.pop();
            j++;
        }
        if (j >= vec.size()) {
            return true;
        }
        if (i >= vec.size()) {
            break;
        }
        stack.push(vec[i++]);
    }
    return false;
};

void dfs(vector<vector<int>>& res,  vector<int>& vec, vector<bool>& used,
         vector<int> candidate) {
    if (candidate.size() == vec.size()) {
        if (checkValid(vec, candidate)) {
            res.push_back(candidate);
        }
        return;
    }
    for (int i = 0; i < vec.size(); i++) {
        if (used[i] == true) {
            continue;
        }
        used[i] = true;
        candidate.push_back(vec[i]);
        dfs(res, vec, used, candidate);
        candidate.pop_back();
        used[i] = false;
    }
}

int main() {
    int a;
    cin >> a;
    vector<int> vec(a);
    for (int i = 0; i < a; i++) {
        cin >> vec[i];
    }
    // 全排列所有的出栈顺序，然后判断出栈顺序是否有效
    vector<vector<int>> res;
    vector<bool> used(a, false);
    vector<int> candidate;
    dfs(res, vec, used, candidate);
    std::sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")