题解 | #火车进站#C++回溯

#include<iostream>
#include<vector>
#include<set>
#include<stack>

using namespace  std;
stack<int>st;
vector<int>path;
set<vector<int>>res;
int n;

void dfs(int next, const vector<int>&ru) {
	if (path.size() == n) {
		res.insert(path);
		return;
	}
	if (next <n)
	{
		st.push(ru[next]);
		dfs(next + 1,ru);
		st.pop();
	}
	if (!st.empty()) {
		int node = st.top();
		path.push_back(node);
		st.pop();
		dfs(next,ru);
		st.push(node);
		path.pop_back();
	}

}


int main() {
	cin >> n;
	vector<int>ru(n);
	for (int i = 0; i < n; i++)
		cin >> ru[i];
	dfs(0,ru);
	for (auto iter = res.begin(); iter != res.end(); iter++) {
		for (int i = 0; i < n; i++)
			cout << (*iter)[i] << " ";
		cout << endl;
	}

}