hello-algo 含重复元素的全排列求解：回溯算法的"相等元素剪枝"与两种剪枝对比

导读

当输入数组包含重复元素时，朴素回溯会生成大量彼此重复的排列。本文以 hello-algo 仓库中「全排列 II」的 PythonTutor 可视化程序（ru/codes/pythontutor/chapter_backtracking/permutations_ii.md）为主体，结合 permutations_ii.py 源码与 permutations_problem.md 理论章节，讲解如何在每轮选择中引入哈希集合 duplicated 实现"相等元素剪枝"，并与去重剪枝 selected 作对比。读完本文，你将能够自己实现一套正确、无重复输出的含重复元素全排列回溯代码，并理解其时间、空间复杂度来源。

一、问题：从"无相等元素"到"可能包含重复元素"

全排列问题是回溯算法的经典应用：给定一个集合（数组或字符串），找出其中元素的所有可能排列。上一节「全排列 I」处理的是不含重复元素的输入，此时 n 个元素共有 n! 种排列，例如：

输入数组	所有排列
[1]	[1]
[1, 2]	[1, 2], [2, 1]
[1, 2, 3]	[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

而「全排列 II」放宽了约束：输入数组中可能包含重复元素（如 [1, 1, 2]），要求返回所有不重复的排列。这也是 hello-algo 中俄语版本可视化文档（位于 ru/codes/pythontutor/chapter_backtracking/permutations_ii.md）所演示的程序核心。

重复从何而来

假设输入数组为 [1, 1, 2]。为了区分两个数值相同的元素，可以把第二个 1 记为 1̂。朴素回溯会同时尝试"先选 1"与"先选 1̂"两条分支，而由于二者数值相等，这两条分支生成的所有排列在结果上两两重复——生成的排列有一半是多余的。因此，最直观的"生成后去重"（借助哈希集合过滤 res）虽然可行，但生成重复排列的搜索分支本身没有必要，应当在搜索过程中提前识别并剪枝，以提升算法效率。

二、相等元素剪枝：让相等的元素在每轮只被选择一次

观察搜索树可知：

• 在第一轮选择中，选择 1 与选择 1̂ 是等价的，二者之下生成的全部排列都是重复的，因此应剪掉 1̂ 这一分支；
• 同理，当第一轮已经选择了 2 之后，第二轮中"选 1 再选 1̂"与"先选 1̂ 再选 1"也会产生重复分支，第二轮里的后出现的相等元素同样要被剪掉。

从本质上看，剪枝目标只有一句话：在某一轮选择中，保证多个相等的元素仅被选择一次。实现方式是在每次调用 backtrack() 时开启一个局部哈希集合 duplicated，记录本轮遍历中已经尝试过的元素值；当 choice 已经在 duplicated 中出现过时直接跳过，即完成剪枝。

三、代码实现与逐步解析

下面是本仓库 codes/python/chapter_backtracking/permutations_ii.py 中的完整实现（可视化文档内嵌的是同一程序的俄语注释版本，代码逻辑完全一致）：

def backtrack(
    state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
    """回溯算法：全排列 II"""
    # 当状态长度等于元素数量时，记录解
    if len(state) == len(choices):
        res.append(list(state))
        return
    # 遍历所有选择
    duplicated = set[int]()
    for i, choice in enumerate(choices):
        # 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
        if not selected[i] and choice not in duplicated:
            # 尝试：做出选择，更新状态
            duplicated.add(choice)  # 记录选择过的元素值
            selected[i] = True
            state.append(choice)
            # 进行下一轮选择
            backtrack(state, choices, selected, res)
            # 回退：撤销选择，恢复到之前的状态
            selected[i] = False
            state.pop()


def permutations_ii(nums: list[int]) -> list[list[int]]:
    """全排列 II"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

对照回溯算法的"状态 / 选择 / 剪枝"三要素，逐段解读如下：

1. 记录解：当 state 的长度等于元素总数 len(choices) 时，说明已构造出一个完整排列。注意这里必须使用 list(state) 复制一份再放入 res，否则后续 state.pop() 会破坏已经记录的结果。
2. 每轮新建 duplicated：duplicated 的生命周期是"一次 backtrack 调用内的一次 for 循环"，这正是相等元素剪枝只作用于同一轮选择的原因。
3. 双重剪枝条件：if not selected[i] and choice not in duplicated 同时校验两类约束：
   • not selected[i]：元素 choices[i] 尚未被选入当前 state（位置剪枝）；
   • choice not in duplicated：本轮循环尚未尝试过该数值（相等元素剪枝）。
4. 尝试与回退：进入分支后先 duplicated.add(choice) 登记本轮已尝试的数值，再置 selected[i] = True、state.append(choice) 递归；返回后执行对称的回退操作 selected[i] = False 与 state.pop()，恢复现场以便尝试其他选择。

四、两种剪枝的对比：selected 与 duplicated 各司其职

selected 和 duplicated 都用于剪枝，但二者的作用域与目标完全不同，docs/chapter_backtracking/permutations_problem.md 中对此有明确归纳：

• 重复选择剪枝（selected）：整个搜索过程只有一个 selected 布尔数组，由最外层 permutations_ii() 一次性创建并贯穿全程。它记录的是当前 state 中已经包含了哪些下标位置的元素，作用是从"位置"维度避免同一元素在排列里出现两次。
• 相等元素剪枝（duplicated）：每个 backtrack 调用（即每一轮选择）各自拥有一个局部 duplicated 集合。它记录的是本轮 for 循环中已经尝试过哪些元素值，作用是从"数值"维度保证相等的元素在一轮之内只被选中一次。

可以这样理解二者的分工：selected 处理"同一个物理元素不能占两个坑"，duplicated 处理"两个数值相等的不同物理元素不能同时抢占同一轮"；两者缺一不可。若只保留 selected，则代码退化为「全排列 I」，会输出重复结果；若去掉 selected，则单个元素可能在一个排列中出现多次。

五、运行验证：输入 [1, 2, 2] 输出 3 个唯一排列

以内嵌在可视化文档中的 Driver Code 为例：

"""Driver Code"""
if __name__ == "__main__":
    nums = [1, 2, 2]

    res = permutations_ii(nums)

    print(f"输入数组 nums = {nums}")
    print(f"所有排列 res = {res}")

期望输出为：

输入数组 nums = [1, 2, 2]
所有排列 res = [[1, 2, 2], [2, 1, 2], [2, 2, 1]]

从数学上验证：3 个元素含两个相等的 2，唯一排列数为 3! / 2! = 3，与程序输出一致。在 PythonTutor 可视化页面中，代码逐行高亮执行并同步展示 state、selected、duplicated、res 四个变量的实时状态，是观察"尝试—剪枝—回退"过程的直观工具：当某轮 choice 命中 duplicated 时，可以看到该行被跳过、不产生递归，这正是剪枝在可视化中的体现。其余语言的等价实现位于各语言的 chapter_backtracking 目录下，例如 permutations_ii.c、permutations_ii.cpp、permutations_ii.java 等，便于跨语言对照学习。

六、复杂度分析

对含重复元素的输入，设元素两两互不相同（最坏情况）时共有 n! 种排列；在记录每个解时需要复制长度为 n 的列表，花费 O(n) 时间，因此时间复杂度为 O(n! · n)。哈希集合 duplicated 的查找与插入在 Python 中平均为 O(1)，不会改变数量级；而实际含重复元素时排列数少于 n!，搜索分支被提前剪掉，运行成本会相应下降。

空间方面：最大递归深度为 n，占用 O(n) 栈帧空间；selected 布尔数组占用 O(n) 空间；而 duplicated 在每一层递归中都会创建一份，同一时刻最多同时存在 n 个 duplicated，每份最多含 n 个元素，合计为 O(n²) 空间，因此空间复杂度为 O(n²)。

七、小结

• 含重复元素的全排列问题，关键不在"事后去重"，而在"事前剪枝"；
• 剪枝需从两个维度同时入手：selected 负责位置去重，duplicated 负责数值去重，二者作用域不同、不可互相替代；
• 时间复杂度 O(n! · n)，空间复杂度 O(n²)；
• 推荐结合本仓库的 PythonTutor 可视化文档（俄语版位于 ru/codes/pythontutor/chapter_backtracking/permutations_ii.md）逐行观察搜索树的展开与回退，再对照各语言源码自行运行验证。

这一"相等元素剪枝"技巧同样适用于「子集和 II」(subset_sum_ii.py) 等其他含重复元素的组合/子集类回溯问题，是回溯剪枝体系中的通用方法论。