【题目来源】
洛谷：P1706 全排列问题 - 洛谷 (luogu.com.cn)
【题目描述】
按照字典序输出自然数 \(1\) 到 \(n\) 所有不重复的排列，即 \(n\) 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
【输入】
一个整数 \(n\)。
【输出】
由 \(1∼n\) 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 \(5\) 个场宽。
【输入样例】
3
【输出样例】
1 2 31 3 22 1 32 3 13 1 23 2 1
【解题思路】
【算法标签】
《洛谷 P1706 全排列问题》 #搜索# #数学# #递归# #深度优先搜索,DFS#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, a[10], book[10] = {0}; // 定义全局变量：n-排列长度，a-存储当前排列，book-标记数组// 深度优先搜索生成全排列
void dfs(int step)
{// step: 当前正在填充的位置索引（从0开始）// 终止条件：已填满整个排列if (step == n) {// 输出当前排列（每个数字占5位宽度）for (int i = 0; i < n; i++) cout << setw(5) << a[i];cout << endl;return;}// 尝试所有可能的数字（1到n）for (int i = 1; i <= n; i++) {// 如果数字i未被使用if (book[i] == 0) {a[step] = i; // 将数字i放入当前位置book[i] = 1; // 标记数字i为已使用dfs(step + 1); // 递归处理下一个位置book[i] = 0; // 回溯，取消数字i的标记}}
}int main()
{cin >> n; // 输入排列长度ndfs(0); // 从第0个位置开始生成排列return 0;
}
#include <bits/stdc++.h>
using namespace std;// 全局变量声明
int n; // 排列长度（1到n的全排列）
int a[10]; // 存储当前生成的排列（索引1到n）
int book[10] = {0}; // 标记数组，记录数字是否已使用（0未使用，1已使用）// 深度优先搜索函数
void dfs(int step)
{// step表示当前正在处理的位置（从1开始）// 终止条件：当step超过n时，说明已经生成了一个完整的排列if (step == n + 1) {// 输出当前排列（每个数字占5位宽度）for (int i = 1; i <= n; i++) cout << setw(5) << a[i]; // 格式化输出cout << endl; // 换行return; // 返回上一层递归}// 尝试将每个数字放入当前位置for (int i = 1; i <= n; i++) {// 检查数字i是否未被使用if (book[i] == 0) {a[step] = i; // 将数字i放入当前位置book[i] = 1; // 标记数字i为已使用dfs(step + 1); // 递归处理下一个位置// 回溯操作a[step] = 0; // 清除当前位置的值（可省略）book[i] = 0; // 取消数字i的标记}}
}int main()
{cin >> n; // 输入排列长度ndfs(1); // 从第1个位置开始生成排列return 0;
}
【运行结果】
31 2 31 3 22 1 32 3 13 1 23 2 1