给出 n 互不相同的数，输出它们的 n！个排列。按字典序从小到大输出这组数的全排列。两个排列在字典序的大小关系指，从第一个位置开始比较，遇到的第一个不相同的数时，较小的那个所在的排列字典序更小。时间限制为一秒钟。使用回溯的方法

使用回溯法求全排列的过程可以这样描述：

首先，将第一个位置的数依次与后面的数交换，然后对后面的数递归进行全排列。递归结束后，需要将交换过的数交换回来，回溯到上一层递归。再将第二个位置的数依次与后面的数交换，以此类推，直到生成所有的排列。

具体实现过程如下：

def backtrack(arr, n, start, res):
    """
    arr: 存储当前排列的数组
    n: 数组的长度
    start: 当前起始位置
    res: 存储所有排列的列表
    """
    if start == n:
        res.append(arr.copy())  # 将当前排列添加到结果中
    else:
        for i in range(start, n):
            arr[start], arr[i] = arr[i], arr[start]  # 交换第 start 个位置和第 i 个位置的数
            backtrack(arr, n, start+1, res)  # 递归生成后面的排列
            arr[start], arr[i] = arr[i], arr[start]  # 回溯到上一层递归，交换回来

n = int(input())
arr = list(range(1, n+1))
res = []
backtrack(arr, n, 0, res)

for perm in res:
    for num in perm:
        print(num, end=' ')
    print()

这样就可以在一秒内生成 n 个数的 n! 个排列，并按字典序从小到大输出。