Codeup_5972：问题 A: 【递归入门】全排列

本文主要是介绍Codeup_5972：问题 A: 【递归入门】全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，所有组合，并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Input

输入一个整数n( 1 <= n <= 10)

Output

输出所有全排列
每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）

Sample Input

Sample Output

原题链接

Codeup_5972：问题 A: 【递归入门】全排列

解题思路

用深度优先搜索遍历所有排列方案，n个数对应n个位置。
用int型数组ans记录已选择数的位置（即全排列方案），用bool型数组visit记录某个数是否被选择。
int类型变量count记录当前已经选择数字的个数，当已选数字个数为n时，表示已经形成全排列（递归边界）。
从第一个位置开始，遍历所有数字（1 ≤ i ≤ n），对每个数字i，有两条路，选择or不选择。
1. 选择：将当前数字i加入全排列数组ans中，并设为已访问，考虑下一个位置（即count + 1）。
2. 不选择：考虑下一个数字（即i+1）。

经验总结

当count == n时，表示已形成全排列，此时dfs应当返回。
但由于visit数组的存在，此处也可以不返回，因为[1，n]范围内的数均被访问过，dfs中的选择过程不会选择任何数。

代码实现（C）

#include <stdio.h>
#include <stdbool.h>
#include <string.h>#define MaxSize 11int n;
bool visit[MaxSize];    // 记录数字是否被访问过
int ans[MaxSize];       // 记录全排列方案// 打印全排列
void print() {for (int i = 0; i < n; ++i) {if (i < n - 1)printf("%d ", ans[i]);elseprintf("%d\n", ans[i]);}
}// 每进行一次DFS,选择一个数字,count记录当前已选择数字的个数
void DFS(int count) {if (count == n) {               // 递归边界:已经选择了n个数print();                    // 打印全排列return;}for (int i = 1; i <= n; ++i) {  // 选择1~n范围内的数字if (!visit[i]) {            // 如果i没被选过ans[count] = i;         // 选择i,加入全排列visit[i] = true;        // 设置i已被访问DFS(count + 1);     	// 继续选择下一个数字// 执行到这说明选择i的路已经走完,该走不选i的路线了(i++)visit[i] = false;       // 设置i未被访问}}}int main() {while (~scanf("%d", &n)) {// 初始化memset(visit, false, sizeof(visit));// 初始时选择了0个数DFS(0);}return 0;
}