#2363. 全排列问题(form.cpp)

全排列问题(form.cpp)

全排列问题(form.cpp)


任务总览

任务名称 时间限制 内存限制 分数
全排列 1 秒 256 MiB 100

题目描述

给定一个整数 n,输出由 1n 组成的所有 不重复 的排列(全排列)。

  • 任何排列中的数字不能重复出现。
  • 输出所有可能的排列,每行一个排列。

输入格式

  • ​**一个整数 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. 递归构造排列​:
    • 选择 1n 中的一个数字作为当前排列的元素。
    • 继续递归选择剩下的数字,直到排列长度等于 n
  2. 回溯剪枝​:
    • 标记数组 记录哪些数字已经使用,避免重复选择。
    • 当排列完成(长度达到 n),就输出结果。

时间复杂度分析

全排列的方案数为 n!,因此时间复杂度为 O(n!)。 由于 ​最大 n 为 9​,9! = 362880,​完全可以接受​。


结论

  • 采用 递归+回溯 方式求解。
  • 剪枝优化 避免重复选取数字。
  • 输出按字典序排列​,符合递归的执行顺序。