def backtrack():
    # 已选够 n 个数，一个完整排列成型，收进结果后返回上一层
    if len(path) == n:
        res.append(' '.join(map(str, path)))
        return
    for x in range(1, n + 1):      # 从小到大，保证字典序
        # 已经用过的数字不能再放，否则一个排列里会出现重复
        if not used[x]:
            # 选它：标记占用，并追加到当前路径末尾
            used[x] = True
            path.append(x)
            # 继续填下一位
            backtrack()
            # 撤销选择，把数字还回去，供同一层的下一个候选使用
            path.pop()
            used[x] = False

第四步：最优解法

回溯法本身就是全排列问题的最优思路，时间复杂度 O(n·n!)（生成 n! 个排列，每个 O(n)），空间 O(n)（回溯栈 + used 数组）。

完整代码实现

import sys


def solve() -> None:
    # 读入一行并转成整数，n 就是要排列的数字个数
    n = int(sys.stdin.readline().strip())

    # res 收集全部排列的字符串形式，path 是当前正在拼的那一个排列
    res = []
    path = []
    # 下标 1..n 对应数字 1..n，多开一格，避免 used[n] 越界
    used = [False] * (n + 1)

    def backtrack():
        # 路径长度达到 n，说明每位都填好了，转成字符串存档
        if len(path) == n:
            res.append(' '.join(map(str, path)))
            return
        for x in range(1, n + 1):      # 从小到大，保证字典序
            # 只考虑还没用过的数字，已用过的会让排列出现重复
            if not used[x]:
                # 做选择：占用 x 并把它放到当前这一位
                used[x] = True
                path.append(x)
                # 递归填下一位
                backtrack()
                # 撤销选择，回到填这一位之前的状态
                path.pop()
                used[x] = False

    # 从空排列开始搜索
    backtrack()
    # 攒够后一次性输出，比在递归里逐行 print 快得多
    print('\n'.join(res))


if __name__ == "__main__":
    solve()