题目描述
- 给定一个整数
n，将数字1∼n排成一排，将会有很多种排列方法。 - 现在，请你按照字典序将所有的排列方法输出。
输入格式
- 共一行，包含一个整数
n。
输出格式
- 按字典序输出所有排列方案，每个方案占一行。
数据范围
1 ≤ n ≤ 7
基本思路
- 本题是深度优先搜索算法（
DFS）的模板题。深度优先搜索是指在存在多个方向选择时，我们选择一条路走到黑，直到走到一条路的终点；然后，从这条路的终点向前回溯，找到上一个岔路口，走没有走过的那条路，继续一条路走到黑，以此类推。 - 在代码实现上，深度优先搜索算法一般都采用递归的函数形式进行实现。这个函数里面一般分为两种情况，也就是“终点”和“岔路口”两种情况，可以通过简单的
if-else语句进行情况判定。对于岔路口的情况，需要做的事情包括“选择一条当前没有走过的路→以该岔路口为起点递归地进行深度优先搜索→深度优先搜索完成后回到该岔路口，然后将状态恢复到本次深度优先搜索之前”
实现代码
#include <cstdio>
// 需要排列的数字个数
int n;
// 用一个数组存储排列中的每一个数字
const int N = 10;
int arrange[N];
// 用一个布尔数组存储已经完成填充的数字
bool numbers[N + 1];
// 基于深度优先搜索的全排列输出函数，输入的数据为当前已经完成填充的数字个数和需要填充的数字总数
void DFS(int filled, int n)
{
// 如果已经找到了一个全排列，则将该全排列输出
if(filled == n)
{
for(int i = 0; i < n; ++ i) printf("%d ", arrange[i]);
printf("\n");
}
// 还没有找到一个全排列，则从剩下的数字中选择下一个插入排列的数字
else
{
for(int i = 1; i <= n; ++ i)
{
// 找到了还没有使用的数字
if(numbers[i] == false)
{
arrange[filled] = i;
numbers[i] = true;
DFS(filled + 1, n);
numbers[i] = false;
}
}
}
}
int main(void)
{
scanf("%d", &n);
DFS(0, n);
return 0;
}
