《Hello 算法》回溯章节精讲：全排列问题的两种剪枝策略与多语言实现

2026-09-06 12:40:51作者：沈韬淼Beryl

本篇基于《Hello 算法》仓库回溯算法章节中的 permutations_problem.md，系统讲解全排列问题的回溯解法：如何把"生成排列"抽象为"一系列选择"的状态空间搜索，如何用 selected 数组做重复选择剪枝、用每轮独立的 duplicated 集合做相等元素剪枝，并结合仓库中 Python、Java、Go 等多语言源码与测试用例，完整呈现从问题定义、递归树分析到复杂度推导的全过程。读完后，你可以独立实现 LeetCode 15/47 类型的排列问题，并能清晰区分两种剪枝条件的生效范围。

一、什么是全排列问题

全排列问题是回溯算法的一个典型应用。其定义是：在给定一个集合（如一个数组或字符串）的情况下，找出其中元素的所有可能的排列。下表列举了几个示例数据，包括输入数组和对应的所有排列。

输入数组	所有排列
`[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]`

文档将全排列拆分为两个由易到难的子问题：

无相等元素的情况：输入一个整数数组，其中不包含重复元素，返回所有可能的排列；
考虑相等元素的情况：输入一个整数数组，数组中可能包含重复元素，返回所有不重复的排列。

二、无相等元素：把排列生成看成"一系列选择"

2.1 回溯三要素：候选集合、状态与唯一性约束

从回溯算法的角度看，我们可以把生成排列的过程想象成一系列选择的结果。假设输入数组为 [1, 2, 3]，如果我们先选择 1，再选择 3，最后选择 2，则获得排列 [1, 3, 2]。回退表示撤销一个选择，之后继续尝试其他选择。

从回溯代码的角度看：

候选集合 choices 是输入数组中的所有元素；
状态 state 是直至目前已被选择的元素。

请注意，每个元素只允许被选择一次，因此 state 中的所有元素都应该是唯一的。

将搜索过程展开成一棵递归树，树中的每个节点代表当前状态 state。从根节点开始，经过三轮选择后到达叶节点，每个叶节点都对应一个排列：

2.2 重复选择剪枝：搜索空间从 O(nⁿ) 降到 O(n!)

为了实现每个元素只被选择一次，考虑引入一个布尔型数组 selected，其中 selected[i] 表示 choices[i] 是否已被选择，并基于它实现剪枝操作：

在做出选择 choices[i] 后，将 selected[i] 赋值为 True，代表它已被选择；
遍历选择列表 choices 时，跳过所有已被选择的节点，即剪枝。

以路径"选 1 → 选 3 → 选 2"为例：第二轮需要剪掉元素 1 的分支，第三轮需要剪掉元素 1 和元素 3 的分支。

观察递归树可以发现，该剪枝操作将搜索空间大小从 $O (n^{n})$ 减小至 $O (n!)$ ——因为每轮实际可选的分支数依次是 $n, n-1, \dots, 1$ ，而未剪枝的完整 $n$ 叉树规模为 $n^{n}$ 。

2.3 代码实现：Python 版全排列 I

想清楚以上信息之后，就可以在框架代码中做"完形填空"了。为了缩短整体代码，仓库中的实现不单独实现框架代码中的各个函数，而是将它们展开在 backtrack() 函数中。完整源码见 permutations_i.py：

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


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

代码结构与回溯模板严格对应：

终止条件：len(state) == len(choices) 说明已做出 $n$ 轮选择，此时复制一份 state（list(state)）记入结果。复制是必须的，否则 state 后续的回退操作会污染已记录的解；
剪枝判断：if not selected[i] 跳过已被占用的元素；
尝试与回退：selected[i] = True、state.append(choice) 之后递归，返回后必须对称地执行 selected[i] = False、state.pop()，才能保证兄弟分支看到一致的状态。

文件末尾附带可直接运行的驱动程序（nums = [1, 2, 3]），输出所有 6 个排列，与上文示例表完全一致。

三、含重复元素：相等元素剪枝

3.1 为什么不能用哈希集合"事后去重"

假设输入数组为 [1, 1, 2]。为了方便区分两个重复元素 1，文档将第二个 1 记为 $\hat{1}$ 。

如果直接套用上一节的 selected 剪枝，生成的 6 个排列中有一半是重复的（例如 [1, \hat{1}, 2] 与 [\hat{1}, 1, 2] 值完全相同）。

那么如何去除重复的排列呢？最直接地，考虑借助一个哈希集合，直接对排列结果进行去重。然而这样做不够优雅，因为生成重复排列的搜索分支没有必要，应当提前识别并剪枝，这样可以进一步提升算法效率。

3.2 相等元素剪枝的原理

观察递归树可以发现：在第一轮中，选择 1 或选择 $\hat{1}$ 是等价的，在这两个选择之下生成的所有排列都是重复的，因此应该把 $\hat{1}$ 剪枝。同理，在第一轮选择 2 之后，第二轮选择中的 1 和 $\hat{1}$ 也会产生重复分支，因此也应将第二轮的 $\hat{1}$ 剪枝。

从本质上看，我们的目标是在某一轮选择中，保证多个相等的元素仅被选择一次。

注意"某一轮"这个限定词：剪枝的作用域是单次 backtrack() 调用内的那一层 for 循环，而非整个搜索过程。

3.3 代码实现与复杂度分析：Python 版全排列 II

在上一题代码的基础上，只需在每一轮选择中开启一个哈希集合 duplicated，用于记录该轮中已经尝试过的元素，并将重复元素剪枝。完整源码见 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

与全排列 I 相比，差异只有两处：函数体内新增 duplicated = set()，以及剪枝条件由 not selected[i] 扩展为 not selected[i] and choice not in duplicated。驱动程序输入 [1, 2, 2]，输出 3 个不重复排列。

复杂度分析（原文档结论）：

假设元素两两互不相同，则 $n$ 个元素共有 $n!$ 种排列（阶乘）；在记录结果时，需要复制长度为 $n$ 的列表，使用 $O (n)$ 时间，因此时间复杂度为 $O(n! \cdot n)$ ；
最大递归深度为 $n$ ，使用 $O (n)$ 栈帧空间；selected 使用 $O (n)$ 空间；同一时刻最多共有 $n$ 个 duplicated 集合（每层递归一个），使用 $O (n^{2})$ 空间，因此空间复杂度为 $O (n^{2})$ 。

3.4 两种剪枝条件的对比

请注意，虽然 selected 和 duplicated 都用于剪枝，但两者的目标不同：

重复选择剪枝：整个搜索过程中只有一个 selected。它记录的是当前状态中包含哪些元素，其作用是避免某个元素在 state 中重复出现；
相等元素剪枝：每轮选择（每个调用的 backtrack 函数）都包含一个 duplicated。它记录的是在本轮遍历（for 循环）中哪些元素已被选择过，其作用是保证相等元素只被选择一次。

下图展示了两个剪枝条件的生效范围。注意，树中的每个节点代表一个选择，从根节点到叶节点的路径上的各个节点构成一个排列：

一个容易踩的坑是误将 duplicated 提升到递归外层、跨轮共享。从源码结构看，duplicated 是 backtrack() 的局部变量，每次进入新的一层递归都会重新创建——这正是"每轮只保证相等元素选一次"这一语义的正确体现；一旦跨轮共享，就会错误地把不同轮次中合法的重复值也剪掉。

四、多语言实现与测试验证

该章节的所有代码均按统一模板实现，仓库在 codes/ 目录下提供了 13 种语言的对应版本，其中与本节直接相关的文件包括：

语言	全排列 I	全排列 II
Python	permutations_i.py	permutations_ii.py
Java	permutations_i.java	permutations_ii.java
Go	permutations_i.go	permutations_ii.go
JavaScript	permutations_i.js	permutations_ii.js

以 Java 版为例，permutations_i.java 中 backtrack() 使用 List<Integer> state、int[] choices、boolean[] selected 三个参数，剪枝判断为 if (!selected[i])，回退操作是对称的 selected[i] = false; state.remove(state.size() - 1);，与 Python 版逐行对应；permutations_ii.java 则对应引入 Set<Integer> duplicated 并在循环条件中追加 !duplicated.contains(choice)。可以看到，无论哪种语言，核心都是同一套"选择 → 递归 → 回退"的模板与两个剪枝条件，便于横向对照学习。

Go 版附带了测试入口 permutation_test.go：TestPermutationI 以 {1, 2, 3} 为输入调用 permutationsI，TestPermutationII 以 {1, 2, 2} 为输入调用 permutationsII，并打印排列结果，可用来验证多语言实现的一致性。Python 版每个文件同样内置 __main__ 驱动程序，直接运行对应 .py 文件即可看到与文档示例一致的输出。

五、小结

本文沿《Hello 算法》全排列问题的原始脉络展开：

状态建模：候选集合 choices + 状态 state + 唯一性约束，把"找排列"转化为在递归树上逐层做选择；
重复选择剪枝：全局唯一的 selected 数组，保证同一元素不进入 state 两次，搜索空间由 $O (n^{n})$ 降至 $O (n!)$ ；
相等元素剪枝：每层递归新建的 duplicated 集合，保证同一轮中相等元素只被选一次，从源头消除重复排列，避免"事后哈希去重"的浪费；
复杂度：时间 $O(n! \cdot n)$ （排列数 $n!$ 乘以复制结果的 $O (n)$ ），空间 $O (n^{2})$ （栈帧与每层一个 duplicated 的叠加）。