C++ 全排列回溯算法详解

该算法是全排列的回溯算法，主要思想是枚举每个位置上可以填的数，然后递归到下一位，直到填满所有位置。

具体实现：

1. 定义一个数组'a'表示当前的排列，数组'b'表示每个数是否被使用过。

2. 从第1个位置开始枚举可以填的数，如果该数没有被使用过，则将其填入'a[x]'中，同时将'b[i]'标记为已使用。

3. 递归到下一位，即'dfs(x+1)'。

4. 在递归结束后，需要将'b[i]'标记为未使用，同时'a[x]'也要清空，方便下次使用。

5. 递归结束条件是'x==n+1'，表示已经填满了所有位置，此时输出当前的排列'a'。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, a[10], b[10];
void dfs(int x) {
	if (x == n + 1) {
		for (int i = 1; i <= n; i++) {
			cout << a[i] << " ";
		}
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (b[i] == 0) {
			b[i] = 1;
			a[x] = i;
			dfs(x + 1);
			b[i] = 0;
			a[x] = 0;
		}
	}
}
int main() {
	cin >> n;
	dfs(1);
	return 0;
}