当前没有测试数据。

题目描述

你需要输出1到n的所有全排列（按字典序）。递归思路：每次从剩余数字中选择一个放在当前位，递归处理后续位置，当排列长度达到n时输出。

请按字典序输出所有排列。

输入格式

一个整数 $n$，满足 $1 \leq n \leq 8$。

输出格式

按字典序输出所有排列，每行一个排列，每个排列由 $n$ 个整数组成（用空格分隔）。

样例

3

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

样例解释

当n=3 时： 递归拆解：先固定首位为1 → 递归处理[2,3] → 得到1 2 3 和 1 3 2 同理固定首位为2 → 递归处理[1,3] → 得到2 1 3 和 2 3 1 最后固定首位为3 → 递归处理[1,2] → 得到3 1 2 和 3 2 1