题目描述

生成 1~n 的所有全排列。

输入格式

一个整数 n（例如 n = 3）。

输出格式

所有可能的排列组合（例如 n = 3时输出 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1）。

样例

输入样例 1

3

输出样例 1

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

输入样例 2

1

输出样例 2

1

输入样例 3

2

输出样例 3

1 2
2 1

提示

解题思路：全排列问题要求生成 1~n 的所有可能排列顺序。回溯法的核心思想是通过递归+状态回退来枚举所有可能性： 1.递归选择：从剩余未使用的数字中选择一个，添加到当前排列中。 2.状态标记：使用一个布尔数组 used记录哪些数字已经被使用过，避免重复选择。3. 回溯撤销：当递归到最深层（排列完成）后，撤销当前选择（将数字标记为未使用），以便尝试其他可能性。