3. 全排列问题（回溯）

【问题描述】

输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

【输入格式】

一个整数n(1≤n≤9)

【输出格式】

按照字典序的顺序输出由 1～n 组成的所有不重复的数字序列，每行一个序列。

【输入样例】

3

【输出样例】

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

#include<bits/stdc++.h>
using namespace std;

int n, a[110];
bool b[110];
 // b[i] 记录 i 这个整数有没有在之前的递归列举中被填写，0表示没有填，1表示填过了  

void f(int x) { // 不仅作为一个参数，代表了当前的递归层数 
	if (x > n) { // x的值超过n的时候，说明已经递归了n次了，已经有n个循环了 
		for (int i=1;i<=n;i++) printf("%d ",a[i]);
		printf("\n"); 
		return;
	}
	for (int i=1;i<=n;i++) { 
		//如果 i 在之前递归中没有被列举到 
		if (b[i]==0) {
			// 如何将不同递归层数当中的枚举出来的数存下来 （设定全局变量） 
			a[x] = i; // 记录，第x层递归枚举出来的数是i 
			b[i] = 1;
			f(x+1);
			// 递归回来的位置 
			b[i] = 0; // i 这个数字又重新可以被使用了 
		}
	}
} // n个1~n的循环在嵌套 
 
int main() {
	scanf("%d",&n);
	// n个循环嵌套，每个循环是1~n，最终删去相同元素方案 
	for (int i=1;i<=n;i++) b[i] = 0; // 初始化，1~n都还没被填写 
	f(1);
	return 0;
}