开发者日记

外观

一文搞懂回溯模板：全排列到组合总和 ​

为什么回溯题总是差一个参数 ​

回溯法本质上是在一棵隐式决策树上做深度优先搜索：选择一个分支、继续递归、离开节点时撤销选择。很多人单独能写出全排列，但一遇到组合总和、子集去重、同一元素不可重复使用等条件，就会在 used、startIndex、排序去重之间反复混淆。

问题通常不在递归本身，而在没有先画清楚回溯树。节点代表“当前已经做出的选择”，边代表“本轮还能选什么”。如果同一层允许选择的元素集合不同，代码入口参数就不同；如果同一个元素在一条深度路径上能否重复出现不同，状态维护方式也不同。

本文用两类高频题串联模板：

  • 全排列：元素顺序不同算不同答案，关注某个元素在当前路径中是否已使用。
  • 组合总和：只看元素集合，不看顺序，关注下一层搜索起点以及剩余目标值。
  • 可重复 / 不可重复 / 数组有重复元素：分别对应递归起点和同层去重策略。

一张图看懂回溯树结构 ​

回溯代码可以抽象成“路径、选择列表、结束条件”。进入节点后判断是否得到答案；然后遍历选择列表，做选择、递归、撤销选择。

进入递归节点path + 状态判断终止条件收集答案后返回遍历选择列表剪枝或同层去重做选择更新 path/used深入下一层start 或全量扫描撤销选择恢复现场

画图时建议只画两到三层，重点标出两件事：

  1. 兄弟节点之间是否允许重复值：这是“同一层去重”，常见写法是排序后判断 nums[i] == nums[i - 1] and not used[i - 1]。
  2. 父子节点之间能否继续选同一个位置：这是“深度路径是否可复用”，决定下一层从 i 还是 i + 1 开始。

全排列模板：顺序敏感，用 used 控制路径 ​

LeetCode 46「全排列」中，[1,2,3] 和 [1,3,2] 是不同答案，因此每一层都要从头扫描所有元素，但已经出现在当前路径中的位置不能再次选择。

python
from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack() -> None:
        # 路径长度等于原数组长度，得到一个完整排列
        if len(path) == len(nums):
            result.append(path.copy())
            return

        for i in range(len(nums)):
            # 当前深度路径上，同一位置不能重复使用
            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack()

            # 离开分支时恢复现场
            path.pop()
            used[i] = False

    backtrack()
    return result


print(permute([1, 2, 3]))

这里没有 start 参数，因为排列关心顺序；例如先选 2 后仍可以回头选 1。used 防的是同一条根到叶子路径上的重复，而不是兄弟分支重复。

如果输入包含重复数字，例如 LeetCode 47「全排列 II」，仅靠 used 会得到 [1a,1b]、[1b,1a] 两份值相同的结果。必须先排序，再在同一层跳过相同值：

python
from typing import List

def permute_unique(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path.copy())
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            # 同一层中，前一个相同数字已经作为兄弟分支搜索过
            # used[i - 1] 为 False 表示它不在当前深度路径上
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


print(permute_unique([1, 1, 2]))

复杂度方面，若元素互不相同，叶子数为 n!，每份答案复制成本为 O(n)，时间复杂度通常写为 O(n × n!)；递归栈和路径长度为 O(n)，不计答案存储时额外空间为 O(n)。

组合总和模板：顺序无关，用 startIndex 消除排列重复 ​

LeetCode 39「组合总和」允许同一个无重复元素被选取多次，但要求的是组合而非排列。为了避免同时生成 [2,3,2] 和 [2,2,3]，要规定后续选择只能从当前下标或之后开始。

python
from typing import List

def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    path = []

    def backtrack(start: int, remain: int) -> None:
        if remain == 0:
            result.append(path.copy())
            return

        for i in range(start, len(candidates)):
            # 排序后，当前数已经大于剩余目标值，后面的数只会更大
            if candidates[i] > remain:
                break

            path.append(candidates[i])

            # 关键：传入 i 而不是 i + 1
            # 表示同一下标在一条深度路径上可以继续使用
            backtrack(i, remain - candidates[i])

            path.pop()

    backtrack(0, target)
    return result


print(combination_sum([2, 3, 6, 7], 7))

start 的作用是固定组合中的非递减顺序。第一层选了下标 2 的数后，下一层只能从下标 2 开始，不能再回到更小下标，因此不会把同一组数字按不同顺序重复记录。

如果题目变为 LeetCode 40「组合总和 II」，每个数字位置最多使用一次，同时数组中可能有重复值，则要同时做两件事：

  • 下一层递归传 i + 1，禁止同一下标重复使用；
  • 排序后在同一层跳过相邻重复值，避免不同位置产生相同组合。
python
from typing import List

def combination_sum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    path = []

    def backtrack(start: int, remain: int) -> None:
        if remain == 0:
            result.append(path.copy())
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break

            # 同一层去重：第一个 1 已经搜索过，就不再用第二个 1 开兄弟分支
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            path.append(candidates[i])

            # 每个位置只能使用一次
            backtrack(i + 1, remain - candidates[i])

            path.pop()

    backtrack(0, target)
    return result


print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))

组合问题的复杂度取决于答案数量 K、单个组合平均长度 L 以及候选数 n。粗略上界为指数级搜索 O(2^n)，复制答案总计 O(KL)；排序成本为 O(n log n)。空间主要是递归栈和路径，通常为 O(target/min) 或 O(n)，具体受目标值、元素最小值和候选数量约束。

三类条件的选型决策框架 ​

可以按下面顺序判断，而不是背多套代码：

题型特征每层扫描范围递归起点去重方式
排列，元素唯一全量扫描无 startused[i]
排列，元素重复全量扫描无 start排序 + used + 同层判重
组合，元素可无限选从 start 扫描传 istart 保证顺序
组合，位置只能选一次从 start 扫描传 i + 1排序 + 同层判重

记忆口诀是：排列看使用状态，组合看搜索起点；重复元素管同层，重复使用管父子。

剪枝也分两类。目标值类题目在排序后可以用 candidates[i] > remain 直接 break，因为后续元素更大；排列类题目通常没有这种单调性，不能随便 break，更多是通过 used 跳过非法分支。

避坑总结：高频错误现象与修正 ​

1. 收集答案时忘记拷贝，最终结果全是空列表 ​

错误现象通常是 result 里打印出多个 []。原因是 result.append(path) 追加的是列表引用，递归返回后执行 path.pop()，外部看到的仍是同一个不断变化的列表。

修正方法是在满足终止条件时写入快照：

python
result.append(path.copy())       # Python
// result.push([...path]);       // JavaScript

2. 组合总和中递归传错起点，出现重复排列或漏解 ​

如果允许重复选择却传了 i + 1，会漏掉 [2,2,3] 这种同一元素多次出现的组合；如果不允许重复选择却传了 i，会把同一个位置反复加入路径。

修正方法是先读题确认“同一个元素”还是“同一个位置”能否重复：无限候选传 i，每个位置最多一次传 i + 1。

3. 数组有重复值时只排序，不做同层去重 ​

典型输入是 [1,1,2] 或组合总和 II 中的两个 1。排序只让重复数字相邻，并不会自动删除重复答案。若把条件写成 i > 0 and nums[i] == nums[i - 1] 而不结合 start 或 used，还可能误杀深度路径上合法的第二个重复元素。

排列中使用：

python
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

组合中由于循环从 start 开始，使用：

python
if i > start and candidates[i] == candidates[i - 1]:
    continue

4. 剪枝前没有排序，却使用 break ​

nums[i] > remain 后直接 break 的前提是数组有序。若输入为 [2, 8, 3]，在目标剩余值为 5 时遇到 8 就退出，会漏掉后面的 3。

修正方法是在回溯开始前统一 sort()；如果不想排序，只能 continue 跳过当前元素，不能假设后续元素也不可行。

掌握这套拆解方式后，大多数回溯题都不需要从零硬想：先判断答案是否关注顺序，再判断元素能否重复使用，最后根据输入是否含重复值补上同层去重。代码模板会变，但回溯树的三条主线——选择、递归、撤销——始终不变。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

本文来自开发者日记（devdiary.cn）· 记录开发者实战笔记与免费在线工具箱

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。