博客

• 提示：使用深度优先搜索解题

Description

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

Input

第一行为一个整数nn

Output

由11至nn组成的所有不重复的数字序列，每行一个序列。每个数字之间由空格隔开。

Sample Input 1

3

标题Sample Output 1

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

Hint

1 \le n \le 91≤n≤9

思路

#include<cstdio>//uncle-lu
/*
对当前的位置进行深度优先搜索，找到每个可以填进去的数进行尝试。搜完了这个位置以后回溯继续搜。
*/
int n;             //定义全局变量；表示我们需要全排列的数
int line[10];      //定义数组记录排序
bool visit[10];    //定义数组记录是否使用过这个数字
void print() {          //打印记录排序数组
	for (int i = 1; i <= n; ++i)
		printf("%d ", line[i]);
	printf("\n");
	return;
}
void dfs(int x){
	if (x > n){
		print();
		return;      //一共n个数都搜完了我们应该返回
	}
	for (int i = 1; i <= n; ++i){
		if (visit[i]) {
			continue;       //如果这个数用过了continue跳过下面的步骤
		}
		else{                  //如果这个数没使用就执行下面的步骤
			visit[i] = true;     //记录使用过i
			line[x] = i;         //将该数i记录进数字排列数组对应的x位置上
			dfs(x + 1);          //继续深搜x + 1 
			visit[i] = false;   //回溯，即搜索结束恢复标记位
		}
	}
	return;
}

int main()
{
	scanf_s("%d", &n);
	dfs(1);
	return 0;
}

重要代码讲解

visit[i] = true; //如果这个数字没使用的话 ，优先标记一下，说明我们接下来就要使用这个了

line[x] = i; //将该数i记录进数字排列数组对应的x位置上（i是每次遍历1->x）

dfs(x + 1); //继续深搜x + 1

visit[i] = false; //回溯，即搜索结束恢复标记位