7-41 输出全排列 作者 DS课程组 单位 浙江大学 请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。 输入格式: 输入给出正整数n（<10）。 输出格式: 输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a 1 ​ ,a 2 ​ ,⋯,a n ​ 排在序列b 1 ​ ,b 2 ​ ,⋯,b n ​ 之前，如果存在k使得a 1 ​ =b 1 ​ ,⋯,a k ​ =b k ​ 并且 a k+1 ​ <b k+1

以下是 Python 3 代码实现：

n = int(input())

def dfs(curr, used):
    if len(curr) == n:
        print("".join(map(str, curr)))
        return
    for i in range(1, n+1):
        if not used[i]:
            used[i] = True
            curr.append(i)
            dfs(curr, used)
            curr.pop()
            used[i] = False

dfs([], [False] * (n+1))

思路解析：

使用 DFS（深度优先搜索）枚举所有可能的全排列。用一个布尔数组 `used` 记录哪些数已经被选过，初始时全部设为 False。每次从 1 到 n 遍历，如果该数没有被选过，则选中它，把它从 `used` 中标记为已选，并把它添加到当前排列 `curr` 中。然后继续递归搜索下一个位置，直到排列长度达到 n，即得到一个合法的全排列，输出它。最后还需要回溯，即撤销上一次的选择，把当前位置的数从 `curr` 中弹出，把它从 `used` 中标记为未选。

时间复杂度分析：

由于本题要输出所有全排列，因此时间复杂度无法避免地是 O(n!)，即 n 的阶乘。实际运行时间取决于计算机的性能和输入的 n 值。当 n 较小时，程序运行时间很短，但当 n 较大时，程序运行时间会急剧增长。因此，本题的运行时间与 n 值之间呈指数级关系。