题解 | 火车进站

#include <iostream>
#include <set>
#include <stack>
using namespace std;

int inSeq[10], vis[10];
int n;

//判断序列是否合法 
bool judge(int *a, int len) {
	//使用双指针
	int p1 = 0, p2; 
	stack<int> st;
  	//stack是不支持st.find的，因此使用set记录
	set<int> s;
	for (p2 = 0; p2 < len; p2++) {
		int val = a[p2];
		if (!st.empty()) {
			if (st.top() == val) {
				st.pop();
				s.erase(val);
				continue;
			} else if (s.find(val) != s.end()) {
				return false;	
			} 
		}
		//入栈
		while (inSeq[p1] != val) {
			st.push(inSeq[p1]);
			s.insert(inSeq[p1]);
			p1++;
		}
		p1++; 
	}
	return true;	
}

//求1 ~ n的全排列 
void dfs(int *a, int deep) {
	if (deep == n + 1) {
		if (judge(a, n)) {
			for (int i = 0; i < n; i++) {
				cout << a[i] << " ";
			}
			cout << endl;
		}
	} 
  	//遍历的顺序就可以解决字典序的要求
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			a[deep - 1] = i;
			vis[i] = 1; 
			dfs(a, deep + 1);
			vis[i] = 0;
			a[deep - 1] = 0; 
		}
	} 
} 

int main() {
	int len;
	cin >> len;
	n = len;
	for (int i = 0; i < len; i++) {
		cin >> inSeq[i];
	}
	int a[10];
	dfs(a, 1);
}