全排列问题（form.cpp）

任务总览

题目描述

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

时间复杂度分析

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

结论

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