数据结构与算法 / 系统课时

画出选择树确定回溯参数

画出选择树确定回溯参数

回溯代码看似总是“选择、递归、撤销”,真正决定写法的是每层能选什么、路径要保存什么,以及何时停止。把搜索过程先画成选择树,就能从树上的信息直接反推出函数参数与剪枝条件。

学习目标

  • 能从选择树中识别每层可选项、路径状态和终止条件
  • 能据此确定回溯函数需要携带的参数
  • 能区分组合、排列等问题在搜索空间上的关键差异

先把题目翻译成选择树

以“从 1..4 中选出 2 个数”为例,根节点表示空路径。第一层可以选择 1、2、3、4;选定一个数后,下一层只能继续选择更大的数,避免生成 [2, 1] 这种与 [1, 2] 重复的组合。

因此,树上的一个节点至少包含两类信息:已经选择的路径,以及下一层允许从哪里开始选。路径长度达到 k 时,节点就是一个完整答案,不再继续向下扩展。

组合问题的回溯选择树

从树反推函数参数

选择树告诉我们,组合问题的递归函数需要一个 start 参数来限制下一层候选范围;当前路径 path 负责记录已经做出的选择;目标长度 k 和候选上界 n 可以由外层作用域提供,不必每次都传入。

如果题目改成全排列,下一层仍可以选择任意未使用元素,此时 start 就不够用了,通常需要 used 数组或位掩码记录哪些元素已经使用。回溯参数应该服务于“描述当前节点”,而不是机械照抄某个模板。

写出组合搜索并验证

下面的程序根据选择树实现组合枚举,并加入一个简单剪枝:如果剩余候选数量已经不足以填满路径,就不再进入那些必然失败的分支。

python
def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path.copy())
            return

        need = k - len(path)
        max_start = n - need + 1

        for value in range(start, max_start + 1):
            path.append(value)
            backtrack(value + 1)
            # 撤销当前选择,让兄弟分支从相同父节点状态继续搜索。
            path.pop()

    backtrack(1)
    return result


if __name__ == "__main__":
    print(combine(4, 2))

预期输出:

text
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

这里的 path.append()、递归调用和 path.pop() 分别对应“沿一条边向下”“继续搜索子树”“返回父节点”。如果画出的树能明确表示这三个动作,代码结构通常就已经确定。

用三个问题检查回溯设计

写回溯前,可以先回答三个问题:当前层有哪些合法候选;进入下一层后哪些信息会变化;什么条件出现时当前路径已经成为答案。回答不清楚时直接写代码,最容易出现重复答案、漏解或终止条件错误。

对于组合问题,搜索树的有效叶子数量是 (nk)\binom{n}{k},复制每个答案还需要 O(k)O(k) 时间,因此输出规模本身就是 O((nk)⋅k)O(\binom{n}{k} \cdot k)。额外递归深度最多为 k。回溯的核心不是背模板,而是让函数参数准确描述选择树上的一个节点。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

画出选择树确定回溯参数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通