hello-algo：回溯算法解排列问题实战——selected 与 duplicated 双重剪枝解析

本文以《Hello 算法》（hello-algo）回溯章节中的排列问题文档为主线，完整讲解全排列问题的回溯建模、两类剪枝（重复选择剪枝与相等元素剪枝）的原理与实现，并结合仓库中 Python 与 Java 的多语言源码，给出经过实际运行的验证结果与复杂度分析。读完本篇，你将掌握「状态 + 选择集 + 剪枝」的回溯三要素如何在排列问题上落地，并能区分 selected 与 duplicated 两种剪枝的作用域差异。

问题定义：枚举全部排列

排列问题（Permutations）是回溯算法的典型应用：给定一个元素集合（如数组或字符串），找出其中所有可能的排列。文档中的示例如下表：

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

文档进一步把问题拆成两个层次递进的子问题：元素互不相同的全排列（Permutations I），以及可能含重复元素、要求输出不重复排列的全排列 II。两者共用同一套回溯骨架，差别只在剪枝条件。

建模：把排列过程看作一系列选择的序列

从回溯的视角看，构建排列的过程就是依次做选择的结果。以输入 [1, 2, 3] 为例：先选 1，再选 3，最后选 2，就得到排列 [1, 3, 2]；「回退」则是撤销某个已做的选择，再尝试其他分支。

落到代码层面，回溯的两个核心变量为：

• 候选集合 choices：输入数组的全部元素；
• 状态 state：当前已经选出的元素序列。

由于每个元素只允许选一次，state 中的元素必须两两互不相同。整个搜索过程可以展开成一棵递归树：每个节点对应一个 state，从根出发经过三轮选择后到达叶子，每个叶子恰好对应一条完整排列。

剪枝一：用 selected 数组防止重复选择

为了让每个元素只被选一次，引入布尔数组 selected，其中 selected[i] 表示 choices[i] 是否已被选中，并据此剪枝：

• 选中 choices[i] 后，置 selected[i] = True，标记该元素已使用；
• 遍历候选 choices 时跳过所有已选元素，即完成剪枝。

以选择顺序 1 → 3 → 2 为例：第二轮需要剪掉元素 1 的分支，第三轮需要剪掉元素 1 和 3 的分支。这种剪枝把搜索空间规模从 $O(n^n)$ 压缩到 $O(n!)$，正是排列数量本身的规模。

代码实现（全排列 I）

文档建议直接在 backtrack() 内部展开「尝试—递归—回退」的三步骨架，而不再单独实现 is_valid、make_choice 等函数。仓库中 Python 版实现 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

可以直接在仓库中运行 codes/python/chapter_backtracking/permutations_i.py 复现，实际输出为：

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

多语言版本中，Java 实现 permutations_i.java 的剪枝与回退逻辑（第 20–34 行）与 Python 版一一对应：if (!selected[i]) 剪枝、selected[i] = true / state.add(choice) 尝试、递归、selected[i] = false / state.remove(...) 回退，体现了同一套回溯模板在不同语言中的统一写法。

剪枝二：用 duplicated 集合剔除相等元素

为什么需要第二轮剪枝

Permutations II 的题目变化为：输入数组可能含重复元素，要求返回不重复的排列。设输入为 [1, 1, 2]，文档用一个技巧来解释问题：把两个相同的 1 记为 $1$ 和 $\hat{1}$ 以作区分。此时若只用上一节的 selected 剪枝，结果中会出现一半的重复排列。

最直接的办法是生成结束后用哈希集合去重，但这不够优雅——产生重复的分支根本不需要被访问，应该提前识别并剪掉，这能进一步提升算法效率。

相等元素剪枝的目标

在第一轮选择中，选 $1$ 和选 $\hat{1}$ 等价，两条分支生成的排列完全相同，因此 $\hat{1}$ 分支应当剪掉；同理，若第一轮选了 2，第二轮中 $1$ 与 $\hat{1}$ 又会产生重复分支，仍需剪掉 $\hat{1}$。一句话概括：目标是在每一轮选择中，多个相等元素只允许被选中一个。

代码实现（全排列 II）

在全排列 I 的基础上，每一轮选择（每次 backtrack 调用）内新建一个哈希集合 duplicated，记录本轮已选过的元素值，从而剪掉重复分支。仓库 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()

注意 duplicated 的声明位置在 for 循环之外、函数体内——它随每次 backtrack 调用创建，作用域仅限当前这一轮选择；而 selected 仍由顶层传入并跨层共享。运行 codes/python/chapter_backtracking/permutations_ii.py 可验证去重效果：

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

Java 版 permutations_ii.java 中对应的是 Set<Integer> duplicated = new HashSet<Integer>() 与判断条件 if (!selected[i] && !duplicated.contains(choice))（第 20–26 行），逻辑与 Python 版一致。

复杂度分析

文档给出的结论是：

• 时间复杂度 $O(n! \cdot n)$：若元素两两不同，$n$ 个元素共 $n!$ 条排列；记录每个结果需拷贝长度为 $n$ 的列表，耗时 $O(n)$。
• 空间复杂度 $O(n^2)$：递归深度最大为 $n$，栈空间 $O(n)$；selected 数组占 $O(n)$；同时最多存在 $n$ 个 duplicated 集合（每层递归各一个），合计 $O(n^2)$。

对比：selected 与 duplicated 两种剪枝的作用域

文档特别强调：两者虽然都用于剪枝，但目标与生命周期截然不同：

剪枝类型	载体	生命周期	记录内容	目的
重复选择剪枝	selected 数组	整个搜索过程仅一个（顶层传入、跨层共享）	哪些元素已进入当前状态 state	保证同一元素不出现在 state 中两次
相等元素剪枝	duplicated 集合	每轮选择（每次 backtrack 调用）各一个	当前这一轮 for 循环中已选过的元素值	保证相等元素在同一轮中只被选一次

需要记住的一点是：递归树的每个节点对应一次选择，根到叶子的路径构成一条排列。selected 沿「纵向」路径生效（同一路径内不重复选同一元素），duplicated 在「横向」同一层内生效（同层内等值元素只保留一条分支）。对照通用回溯模板（见 backtracking_algorithm.md 中 is_valid(state, choice) 剪枝检查的位置），这两个条件正是被折叠进该判断里的具体实例。

仓库中的复现入口

本篇涉及的实现与素材在 hello-algo 仓库中的位置如下，可按需查看或运行：

• 文档原文（俄语版）：permutations_problem.md；
• Python 实现：permutations_i.py、permutations_ii.py，直接以 python3 运行即可看到示例输出；
• Java 实现：permutations_i.java、permutations_ii.java，均带 main 方法可直接执行；
• 仓库 codes/ 目录下同时提供 C、C++、C#、Go、JavaScript、Rust、Swift、Kotlin、TypeScript、Dart 等十余种语言的同名实现，剪枝逻辑在各语言中保持一致，便于横向对比。

综上，排列问题用最小的规模完整展示了回溯算法的全部要素：状态与选择集的建模、递归树搜索、「尝试—递归—回退」骨架，以及按问题约束定制的两类剪枝。掌握 selected（纵向去重）与 duplicated（横向等值剪枝）的作用域区分后，即可将同一套思路迁移到文档同章节的 N 皇后、子集求和等更复杂的约束搜索问题中。