跳到主要内容

回溯法生成排列

核心思路是：在递归深度 kk 时，决定由哪个未使用的输入位置来填充输出的第 kk 位。

这里的关键在于跟踪“位置”而不仅仅是“值”。如果只跟踪值，当输入包含重复元素时，很难正确区分哪些是重复的排列，哪些是合法的。通过标记位置的使用状态，我们可以精确控制元素的复用逻辑。

def unique_permutations(values: list[int]) -> list[list[int]]:
    values = sorted(values)
    used = [False] * len(values)
    path: list[int] = []
    result: list[list[int]] = []

    def visit() -> None:
        if len(path) == len(values):
            result.append(path.copy())
            return
        for i, value in enumerate(values):
            if used[i]:
                continue
            # 剪枝关键：如果当前值与前一个值相同，且前一个值未被使用，则跳过
            # 这保证了相同值的元素必须按顺序被选取，避免生成重复排列
            if i > 0 and value == values[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(value)
            visit()
            path.pop()
            used[i] = False

    visit()
    return result

去重原理： 首先对输入数组排序，将相同的值聚集在一起。在每一层决策中，如果当前值与前一个值相同，且前一个值尚未被使用（not used[i - 1]），则跳过当前值。

这条规则强制相同值的元素必须按照它们在数组中的顺序被选取。例如，对于两个相同的 1，必须先选第一个 1 才能选第二个 1。这样就剪掉了所有因相同值交换位置而产生的对称分支，同时保留了所有本质不同的排列。

复杂度分析​

  • 输出规模：若 nn 个值互不相同，共有 n!n! 种排列，每种长度为 nn。生成并存储所有结果需要 Θ(n⋅n!)\Theta(n \cdot n!) 的时间和空间。
  • 额外开销：回溯过程本身需要 O(n)O(n) 的空间来维护路径（path）、使用状态（used）以及递归栈。

如果不需要一次性获取所有结果，可以使用生成器（Generator）逐个产出排列。这样可以避免存储完整的输出列表，节省内存，但无法改变生成所有排列所需的时间下界。

重复值跟踪与空排列​

输入 [1,1,2] 时，根层可选第一个 1 或 2，但跳过第二个 1。选了第一个 1 后，第二个 1 就可用了：接着选它得到 [1,1,2]，接着选 2 则得到 [1,2,1]。根层从 2 开始的分支得到 [2,1,1]。因此保留了必需的两份 1，只去掉可互换的位置身份。

每次递归路径都增长一位，最多 n 位，故必然终止。空输入返回 [[]]，而非 []：零个元素恰有一种排列。若各值重数为 m₁,…,mᵣ，不同输出数为 n!/(m₁!…mᵣ!)。代码在每个内部节点仍扫描 n 个位置，不能据此断言运行时间总与不同输出数成正比。所有值相同时只有一个输出，但扫描工作为 Θ(n²)。

assert unique_permutations([1, 1, 2]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
assert unique_permutations([]) == [[]]

参考​

探索关联

被引用 (1)

同主题的其他笔记 (35)

打开关联网络