hello-algo 回溯算法实战：全排列 II（含重复元素）的 Python 实现、剪枝原理与多语言对照

本文基于《Hello 算法》仓库中的 Python Tutor 标注文档 permutations_ii.md，系统讲解“全排列 II”（输入数组可能含重复元素，返回所有不重复排列）的完整实现。读完后你将掌握：如何在线性表上实现状态压缩（selected 标记数组）、如何用每轮独立的哈希集合 duplicated 对“相等元素”做剪枝、该剪枝为何比“结果去重”更高效，以及时间/空间复杂度的推导方式，并能把同一套回溯思路迁移到 Java、Go 等其他语言的实现中。

一、这个 pythontutor 标注文档是什么

仓库中 codes/pythontutor/ 目录存放的并不是可直接运行的脚本，而是为每道算法题生成的 Python Tutor 逐步可视化标注文件。以 permutations_ii.md 为例，文件结构固定为两部分：

1. 元信息注释头：包含文件名、创建时间（2024-01-05）、作者（krahets）；
2. 一行核心注释 + 一条渲染链接：

<!-- [file]{permutations_ii}-[class]{}-[func]{permutations_ii} -->
https://pythontutor.com/render.html#code=...&py=311&curInstr=13...

这行注释 [file]{permutations_ii}-[class]{}-[func]{permutations_ii} 是该仓库文档渲染插件的占位标记，用于在《Hello 算法》书中自动嵌入对应的多语言代码块，它指明本题对应源文件为 permutations_ii、目标函数为 permutations_ii()。紧随其后的链接则是 Python Tutor 的可视化页面地址，链接的查询参数把整段 Python 源码做了 URL 编码后内嵌其中：

• code= 参数中编码的内容，与仓库中 permutations_ii.py 的源码逐行一致（backtrack 递归函数 + permutations_ii 入口函数 + __main__ 驱动代码）；
• py=311 表示按 Python 3.11 语义执行；
• curInstr=13 指定页面打开时默认停在第 13 条指令处（即递归入口附近），方便读者从关键位置开始逐步观察状态变化。

也就是说，这份标注文档的作用是让读者在网页上逐行“单步执行”全排列 II 的完整代码，观察 state、selected、duplicated 三个数据结构在每一轮递归中的演化。下面结合仓库源码还原这段代码的完整内容与设计意图。

二、问题定义：从“全排列 I”到“全排列 II”

《Hello 算法》回溯章节（见 permutations_problem.md）将排列问题拆成两档：

• 全排列 I：输入不含重复元素，如 [1, 2, 3] 有 3! = 6 种排列；
• 全排列 II：输入可能包含重复元素，需返回所有不重复的排列，如 [1, 2, 2] 只有 3 种排列。

以输入 [1, 1, 2]（为方便区分，记第二个 1 为 1̂）为例：如果直接使用全排列 I 的算法，会得到一半重复的排列，因为“第一轮选 1”与“第一轮选 1̂”生成的子树完全等价。因此朴素做法会做大量无用功。

仓库中 permutations_i.py 就是前一档的实现：其剪枝条件只有 if not selected[i]，保证每个元素最多被选一次。而本文的主角 permutations_ii.py 在此基础上多了一个 duplicated 集合，下面逐层拆解。

三、Python 实现逐行解析

仓库 Python 版本完整代码如下（源码路径 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

3.1 四个参数的职责

参数	类型	作用
state	list[int]	当前路径状态，即“到目前为止已选出的元素序列”
choices	list[int]	候选集合，即输入数组本身（全排列场景下候选集固定为全部元素）
selected	list[bool]	长度与 choices 相同的布尔标记数组，selected[i] 表示第 i 个元素是否已被选中，实现“重复选择剪枝”
res	list[list[int]]	结果列表，按引用传入，使所有递归层共享同一个容器

入口函数 permutations_ii 的初始化值得注意：selected=[False] * len(nums) 一次性构造全 False 的标记数组；state=[] 表示从空路径出发；res 以引用传递，避免每层递归新建结果容器。

3.2 递归骨架：终止、尝试、递归、回退

backtrack 函数体现了标准的回溯四步结构：

1. 终止条件：len(state) == len(choices) 说明已选满 n 个元素，一条完整排列形成。此处用 res.append(list(state)) 复制当前状态再入列——因为 state 是共享的可变列表，后续 pop() 会不断改动它，若直接存引用，最终结果会全部变成空列表；
2. 遍历选择：for i, choice in enumerate(choices) 枚举所有候选。循环前先创建本轮专属的 duplicated = set[int]()；
3. 剪枝 + 尝试：条件 not selected[i] and choice not in duplicated 同时校验两个约束（见下节详解）。通过后执行三步“做选择”：duplicated.add(choice) 记录值、selected[i] = True 占位、state.append(choice) 扩展路径；
4. 递归 + 回退：backtrack(...) 进入下一轮选择；返回后必须原路撤销刚才的三步——selected[i] = False、state.pop()，恢复到进入本轮前的状态，才能继续尝试其他候选。注意 duplicated 无需手动清理，因为它随函数帧结束自然销毁（每轮一个独立集合）。

3.3 关键设计：为什么 duplicated 只在单轮内生效

这是本题最容易被误解的一点，也是官方文档 permutations_problem.md 中“两种剪枝对比”小节的重点：

• 重复选择剪枝（selected）：整个搜索过程只有一个 selected，它是全局的。作用是把“同一位置 i 的元素”从 state 中排除，防止某个元素被重复占用；
• 相等元素剪枝（duplicated）：每一轮选择（即每次 backtrack 调用、每个 for 循环）都新建一个 duplicated。它只记录本轮已尝试过的元素值，作用是在同一轮中保证相等元素只被选一次。

以输入 [1, 1, 2] 的第一轮为例：遍历到第 1 个 1 时会执行 duplicated.add(1)；紧接着遍历第 2 个 1（1̂）时，1 已在 duplicated 中，该分支直接被剪掉——而这正是剪枝的本质：在第一轮中，选 1 与选 1̂ 是完全等价的，二者生成的所有排列都互为重复，所以保留任意一个即可。同理，第一轮选了 2 之后的第二轮中，两个 1 也会被剪掉一个。

反过来说，duplicated 的作用范围不能跨轮：第一轮的 duplicated 销毁后，第二轮会新建一个空集合，因此 [1, 1, 2] 的排列 [1, 1, 2] 依然合法——两个 1 分属不同轮次、位于 state 的不同位置，并不构成重复排列。图中每个节点代表一次选择，从根到叶的路径构成一个排列，可直观看到两种剪枝各自生效的范围：

四、复杂度分析

以文档 permutations_problem.md 的推导为准：

• 时间复杂度 O(n!·n)：元素两两不同时，排列数为 n!；每记录一个结果需复制长度为 n 的列表，耗时 O(n)。相等元素剪枝只是进一步压缩了实际搜索的分支数，不会改变最坏量级；
• 空间复杂度 O(n²)：最大递归深度为 n，栈帧 O(n)；selected 数组 O(n)；关键在于 duplicated 集合——同一时刻递归栈上最多有 n 个 backtrack 调用帧，每帧持有一个 duplicated，大小最多 n，合计 O(n²)。

这个 O(n²) 的额外空间正是“提前剪枝”方案的代价，换来的是不再生成任何重复排列的分支——文档明确指出，直接对结果做哈希去重虽然可行，但“生成重复排列的搜索分支没有必要，应当提前识别并剪枝”。

五、多语言实现对照

同一套算法在仓库各语言目录下均有等价实现，核心结构完全一致，可作为跨语言迁移的参照：

• Java（permutations_ii.java）：duplicated 用 HashSet<Integer> 实现，剪枝条件写为 !selected[i] && !duplicated.contains(choice)；回退步用 state.remove(state.size() - 1) 移除末尾元素；
• Go（permutations_ii.go）：duplicated 用空结构体 map map[int]struct{}{} 充当集合（省内存写法），且由于 Go 切片 append 可能触发扩容，四个参数全部以指针传递，入列结果前用 append([]int{}, *state...) 显式拷贝一份快照。

各语言版 __main__/main 的驱动代码均使用同一测试用例 nums = [1, 2, 2]，运行 Python 版可验证：

python3 codes/python/chapter_backtracking/permutations_ii.py
# 输出：
# 输入数组 nums = [1, 2, 2]
# 所有排列 res = [[1, 2, 2], [2, 1, 2], [2, 2, 1]]

六、小结与延伸阅读

本篇围绕仓库的 Python Tutor 标注文件 permutations_ii.md 还原并深挖了“全排列 II”的实现要点：

1. state / choices / selected / res 四参数构成可复用的回溯骨架；
2. 剪枝由两层独立完成：全局 selected 防“同一元素被重复占用”，每轮局部 duplicated 防“相等元素在同轮被重复选择”；
3. 终止处必须拷贝 state，回退处必须精确撤销 selected 与 state 的变更；
4. 代价与收益：O(n²) 辅助空间换取零重复分支的搜索过程。

若需继续延伸，可参考同目录的其他回溯题标注文件（如 permutations_i.md、subset_sum_i.md）以及正文 permutations_problem.md 中全排列 I 的递归树与剪枝示意图，理解“选择—递归—回退”这一范式在不同问题形态下的变形。