数据结构与算法 / 系统课时
画出选择树确定回溯参数
画出选择树确定回溯参数
回溯代码看似总是“选择、递归、撤销”,真正决定写法的是每层能选什么、路径要保存什么,以及何时停止。把搜索过程先画成选择树,就能从树上的信息直接反推出函数参数与剪枝条件。
学习目标
- 能从选择树中识别每层可选项、路径状态和终止条件
- 能据此确定回溯函数需要携带的参数
- 能区分组合、排列等问题在搜索空间上的关键差异
先把题目翻译成选择树
以“从 1..4 中选出 2 个数”为例,根节点表示空路径。第一层可以选择 1、2、3、4;选定一个数后,下一层只能继续选择更大的数,避免生成 [2, 1] 这种与 [1, 2] 重复的组合。
因此,树上的一个节点至少包含两类信息:已经选择的路径,以及下一层允许从哪里开始选。路径长度达到 k 时,节点就是一个完整答案,不再继续向下扩展。

从树反推函数参数
选择树告诉我们,组合问题的递归函数需要一个 start 参数来限制下一层候选范围;当前路径 path 负责记录已经做出的选择;目标长度 k 和候选上界 n 可以由外层作用域提供,不必每次都传入。
如果题目改成全排列,下一层仍可以选择任意未使用元素,此时 start 就不够用了,通常需要 used 数组或位掩码记录哪些元素已经使用。回溯参数应该服务于“描述当前节点”,而不是机械照抄某个模板。
写出组合搜索并验证
下面的程序根据选择树实现组合枚举,并加入一个简单剪枝:如果剩余候选数量已经不足以填满路径,就不再进入那些必然失败的分支。
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))预期输出:
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]这里的 path.append()、递归调用和 path.pop() 分别对应“沿一条边向下”“继续搜索子树”“返回父节点”。如果画出的树能明确表示这三个动作,代码结构通常就已经确定。
用三个问题检查回溯设计
写回溯前,可以先回答三个问题:当前层有哪些合法候选;进入下一层后哪些信息会变化;什么条件出现时当前路径已经成为答案。回答不清楚时直接写代码,最容易出现重复答案、漏解或终止条件错误。
对于组合问题,搜索树的有效叶子数量是 ,复制每个答案还需要 时间,因此输出规模本身就是 。额外递归深度最多为 k。回溯的核心不是背模板,而是让函数参数准确描述选择树上的一个节点。