#2363. 全排列问题(form.cpp)
全排列问题(form.cpp)
全排列问题(form.cpp)
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
全排列 | 1 秒 | 256 MiB | 100 |
题目描述
给定一个整数 n
,输出由 1
到 n
组成的所有 不重复 的排列(全排列)。
- 任何排列中的数字不能重复出现。
- 输出所有可能的排列,每行一个排列。
输入格式
- **一个整数
n
**(1 ≤ n ≤ 9
)。
输出格式
- 每行一个排列,每个排列由 1 到 n 组成,数字 之间用空格分隔。
样例
输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
题目分析
全排列是一个典型的 递归+回溯 问题。
- 递归构造排列:
- 选择
1
到n
中的一个数字作为当前排列的元素。 - 继续递归选择剩下的数字,直到排列长度等于
n
。
- 选择
- 回溯剪枝:
- 用 标记数组 记录哪些数字已经使用,避免重复选择。
- 当排列完成(长度达到
n
),就输出结果。
时间复杂度分析
全排列的方案数为 n!
,因此时间复杂度为 O(n!)
。
由于 最大 n
为 9,9! = 362880
,完全可以接受。
结论
- 采用 递归+回溯 方式求解。
- 剪枝优化 避免重复选取数字。
- 输出按字典序排列,符合递归的执行顺序。