题解：AcWing 842 排列数字

【题目来源】

AcWing：842. 排列数字 - AcWing题库

【题目描述】

给定一个整数 ，将数字 \(1\sim n\) 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

【输入】

共一行，包含一个整数 \(n\)。

【输出】

按字典序输出所有排列方案，每个方案占一行。

【输入样例】

3

【输出样例】

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

【解题思路】

【算法标签】

《AcWing 842 排列数字》 #DFS#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 10;  // 定义最大数字范围int n;          // 输入的数字n（排列长度）
int path[N];    // 存储当前路径（排列结果）
bool st[N];     // 标记数字是否已被使用// 深度优先搜索生成全排列
void dfs(int u)  // u: 当前处理的位置
{// 终止条件：已填满所有位置if (u == n) {// 输出当前排列for (int i = 0; i < n; i++) printf("%d ", path[i]);puts("");  // 换行return;}// 遍历所有可能的数字选择for (int i = 1; i <= n; i++) {// 如果数字i未被使用if (!st[i]) {path[u] = i;    // 选择数字i放入当前位置st[i] = true;   // 标记数字i已使用dfs(u + 1);     // 递归处理下一个位置st[i] = false;  // 回溯：恢复数字i的可用状态}}
}int main()
{cin >> n;    // 输入排列长度dfs(0);      // 从第0个位置开始生成排列return 0;
}

【运行结果】

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