0 Basic

  1. 什么是回溯？ 回溯是在“解空间树”上做DFS，进入分支时选择，退出分支时撤销选择

  2. 模板：考虑

    • 路径path: 已经做出的选择，如一个全局list
    • 选择列表：当前层还能做的选择，如for loop范围
    • 终止条件：长度/和等等
 1def backtrack(path, 选择列表):
 2    if 满足终止条件:
 3        res.append(path[:])          # 注意拷贝
 4        return
 5        
 6    for 选择 in 选择列表:
 7        if 不合法(选择):
 8            continue / break          # 剪枝
 9        path.append(选择)             # ① 做选择
10        backtrack(path, 新的选择列表)  # ② 递归
11        path.pop()                   # ③ 撤销
  1. 收集时期：全节点收集 vs 叶子收集 
 1# 子集型：树上每个节点都是一个合法答案
 2def dfs(start):
 3    res.append(path[:])        # 写在开头，不 return
 4    for i in range(start, n):
 5        ...
 6
 7# 排列/定长组合：只有叶子是答案
 8def dfs():
 9    if len(path) == n:
10        res.append(path[:]); return   # 写在终止条件里
11    for i in range(n):
12        ...
  1. 复杂度估计：总时间 = 树的节点数 × 每个节点的处理代价
题节点 / 叶子数单节点代价复杂度
78 子集2ⁿ 个节点拷贝 O(n)O(n · 2ⁿ)
46 全排列n! 个叶子拷贝 O(n)O(n · n!)
77 组合C(n,k) 个叶子O(k)O(k · C(n,k))
22 括号生成第 n 个卡特兰数 CₙO(n)O(n · Cₙ)
79 单词搜索每步最多 3 个新方向O(1)O(m·n·3^L)
51 N 皇后≤ n!O(n)O(n!)

经验：n ≤ 20 才敢直接写纯回溯（2²⁰ ≈ 10⁶）；排列型n ≤ 10（10! ≈ 3.6×10⁶）。数据范围超了，就该往 DP / 记忆化想

  1. 四问定位
题Q1 顺序有关Q2 可重复选Q3 原数组有重复Q4 要几个解控制手段
78 子集无关否否全部start
90 子集 II无关否是全部start + 同层去重
77 组合无关否否全部start + 数量剪枝
39 组合总和无关是否全部start，递归传 i
40 组合总和 II无关否是全部传 i+1 + 同层去重
46 全排列有关否否全部used
47 全排列 II有关否是全部used + 同层去重
17 电话号码位置固定——全部层号 idx
131 分割回文串位置固定——全部start = 下一段起点
51 N 皇后逐行放——全部三个集合
37 解数独逐格填——一个返回 bool

1 排列型

为什么排列型不能用start？

  • start只会往后走，永远走不出[3, 2, 1]这种回头解

1.1 全排列 | Medium

题目： 给定不含重复数字的数组 nums，返回所有可能的全排列 [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路分析：四问定位

  • 和顺序有关：用used数组，每层从0开始扫
  • 不可以重复选
  • 原数组不含重复数字，无需去重
  • 所有答案都要

踩坑记录：

  • 拷贝答案要用path[:]，path时饮用，之后会被修改

代码：

 1class Solution:
 2    def permute(self, nums: List[int]) -> List[List[int]]:
 3        n = len(nums)
 4        used = [False] * n
 5        res, path = [], []
 6
 7        def dfs():
 8            if len(path) == n:
 9                res.append(path[:])
10                return 
11            
12            for i in range(n):
13                if used[i]:
14                    continue
15                used[i] = True
16                path.append(nums[i])
17                dfs()
18                used[i] = False
19                path.pop()
20        dfs()
21
22        return res

复杂度：

  • 时间 O(n × n!)
  • 空间 O(n)

1.2 全排列 II | Medium

题目：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列

思路分析：四问定位

  • 和顺序有关：用used数组
  • 不可以重复选
  • 原数组有重复的，所以需要排序 + 去重
  • 所有答案都需要

踩坑记录：

  • 去重标准：剪兄弟不剪父子 i > 0 and nums[i] == nums[i - 1] and not used[i - 1]
  • 如[1, 1, 2]：
    • 不剪父子：第一个位置选第一个1， used[0] = True, 然后继续选第二个位置[1, 1, 2]，第一个1 used[0] = True所以不能选了，第二个1not used[0] = False所以还可以选
    • 剪兄弟：第一个位置选第二个1，used[0] = False，判断去重时not used[0] = True: continue

代码：

 1class Solution:
 2    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
 3        nums.sort()
 4        n = len(nums)
 5        used = [False] * n
 6        res, path = [], []
 7
 8        def dfs():
 9            if len(path) == n:
10                res.append(path[:])
11                return
12            for i in range(n):
13                if used[i]:
14                    continue
15                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
16                    continue
17                used[i] = True
18                path.append(nums[i])
19                dfs()
20                used[i] = False
21                path.pop()
22        dfs()
23
24        return res

复杂度：

  • 时间 O(n × N), N = n! / (c₁!·c₂!·…·cₘ!)
  • 空间 O(n)

2 子集型

特征：树上每个节点都是答案，解的个数 2ⁿ 级别

2.1 子集 | Medium

题目： 给定不含重复元素的数组 nums，返回所有可能的子集 [1,2,3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

思路分析：四问定位

  • 和顺序无关：对于每个元素只有选和不选两个选择，用start索引保证子集不重复（只往后选，不回头）
  • 不可以重复选：dfs(i + 1)
  • 原数组无重复：无需排序
  • 所有答案都需要
start=0          []
               / | \
start=1     [1] [2] [3]
            / \   |
start=2  [1,2][1,3][2,3]
           |
        [1,2,3]

踩坑记录：

  • 选择列表和dfs传参数

代码：

 1class Solution:
 2    def subsets(self, nums: List[int]) -> List[List[int]]:
 3        n = len(nums)
 4        res, path = [], []
 5
 6        def dfs(start):
 7            res.append(path[:])
 8            for i in range(start, n):
 9                path.append(nums[i])
10                dfs(i + 1)
11                path.pop()
12        dfs(0)
13
14        return res

复杂度：

  • 时间 O(n × $2^n$)
  • 空间 O(n)

2.2 子集 II | Medium

题目：一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）

思路分析：四问定位

  • 和顺序无关：用start传递参数
  • 不可以重复选:dfs(i + 1)
  • 原数组有重复：排序 + 去重
  • 所有答案都需要

踩坑记录：

  • 去重

代码：

 1class Solution:
 2    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
 3        nums.sort()
 4        n = len(nums)
 5        res, path = [], []
 6
 7        def dfs(start):
 8            res.append(path[:])
 9            for i in range(start, n):
10                if i > start and nums[i] == nums[i - 1]:
11                    continue
12                path.append(nums[i])
13                dfs(i + 1)
14                path.pop()
15        dfs(0)
16
17        return res

复杂度：

  • 时间 (n · N)，N = ∏(cᵢ + 1) 是去重后的子集数
  • 空间 O(n)

3 组合型 · 定长

特征：解的长度固定为 k，只在叶子收集。相比子集型多了数量剪枝

3.1 组合 | Medium

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合

思路分析：四问定位

  • 和顺序无关：用start
  • 不可以重复选
  • 原始无重复
  • 所有答案都需要

踩坑记录：

  • 剪枝分析：range(start, n - (k - len(path)) + 2)
  • 假设当前还需要need = k - len(path)个数，如果这一层选i，那么从i开始到n一共有n - i + 1个数可以用，必须need <= n - i + 1 $\Rightarrow$ i <= n - need + 1

代码：

 1class Solution:
 2    def combine(self, n: int, k: int) -> List[List[int]]:
 3        res, path = [], []
 4
 5        def dfs(start):
 6            if len(path) == k:
 7                res.append(path[:])
 8                return
 9
10            need = k - len(path)
11            for i in range(start, n - need + 2):
12                path.append(i)
13                dfs(i + 1)
14                path.pop()
15        dfs(1)
16
17        return res

复杂度：

  • 时间 O(k · C(n,k))
  • 空间 O(k)

3.2 组合总和 III | Medium

题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

思路分析：四问定位

  • 和顺序无关
  • 不可以重复选
  • 原数组无重复
  • 所有答案都需要

踩坑记录：

  • 数量剪枝：同上，need = k - len(path)，剩下9 - i + 1 = 10 - i个数，所以need <= 10 - i即i <= 10 - need
  • 总和剪枝：我们是从小到大扫描的，所以当total + i > target/n时，可以剪枝（后面也更大）

代码：

 1class Solution:
 2    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
 3        res, path = [], []
 4
 5        def dfs(start, total):
 6            if len(path) == k:
 7                if total == n:
 8                    res.append(path[:])
 9                return 
10
11            need = k - len(path)
12            for i in range(start, 11 - need):
13                if total + i > n:
14                    break
15                path.append(i)
16                dfs(i + 1, i + total)
17                path.pop()
18        dfs(1, 0)
19
20        return res

复杂度：

  • 时间 O(k · C(9,k))
  • 空间 O(k)

4 组合型 · 目标和

特征：不再限制长度，而是限制"和 = target

4.1 组合总和 | Medium

题目：给定无重复元素的正整数数组 candidates 和目标数 target，找出所有和为 target 的组合。每个数字可以无限次使用。 candidates = [2,3,6,7], target = 7 → [[2,2,3], [7]]

思路分析：四问定位

  • 和顺序无关：用start
  • 可以重复选：dfs(i,...)
  • 原数组无重复
  • 所有答案

踩坑记录：

  • 先排序
  • 数值剪枝:total + candidates[i] > target: break，因为排序所以后面一定更大
  • 可以重复选

代码：

 1class Solution:
 2    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
 3        candidates.sort()
 4        n = len(candidates)
 5        res, path = [], []
 6
 7        def dfs(start, total):
 8            if total == target:
 9                res.append(path[:])
10                return 
11
12            for i in range(start, n):
13                if total + candidates[i] > target:
14                    break
15                path.append(candidates[i])
16                dfs(i, total + candidates[i])
17                path.pop()
18        dfs(0, 0)
19
20        return res

复杂度：

  • 时间 O(n · Cᵗ)
  • 空间 O(t/m)
  • 其中 t = target，m = min(candidates)

4.2 组合总和 II | Medium

题目：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次

思路分析：四问定位

  • 和顺序无关
  • 不可以重复选：dfs(i + 1, ...)
  • 原数组有重复：排序 + 去重
  • 所有答案

踩坑记录：

  • 数值剪枝：
  • 重复去重：

代码：

 1class Solution:
 2    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
 3        candidates.sort()
 4        n = len(candidates)
 5        res, path = [], []
 6
 7        def dfs(start, total):
 8            if total == target:
 9                res.append(path[:])
10                return 
11            for i in range(start, n):
12                if total + candidates[i] > target:
13                    break
14                if i > start and candidates[i] == candidates[i - 1]:
15                    continue
16                path.append(candidates[i])
17                dfs(i + 1, total + candidates[i])
18                path.pop()
19        dfs(0, 0)
20
21        return res

复杂度：

  • 时间 O(n · 2ⁿ)
  • 空间 O(n)

5 棋盘约束型

5.1 N 皇后 | Hard

题目： 在 n×n 棋盘上放 n 个皇后，使它们不能互相攻击（同行、同列、同对角线不能有两个皇后）。返回所有解

思路分析： 每个皇后放置位置有：行约束，列约束，主对角线约束，副对角线约束 所以我们逐行放置，天然避免行冲突；在row行，我们枚举所有列[0,1,...,n-1]，每个位置进行三重判断：列，主对角线，副对角线，如果都不冲突则选择该位置同时进入三个集合，然后我们递归到下一行dfs(row + 1)，返回后撤销，当row == n时，n行全部放完，把当前路径放进结果中

方阵特点: 当前位置[r, c]

  • 主对角线满足：r - c相等
  • 副对角线满足：r + c相等

踩坑记录：

  • queens代表每行放的列位置

代码：

 1class Solution:
 2    def solveNQueens(self, n: int) -> List[List[str]]:
 3        res, queens = [], []
 4        cols, d1, d2 = set(), set(), set()
 5
 6        def dfs(r):
 7            if r == n:
 8                res.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
 9                return 
10            for c in range(n):
11                if c in cols or (r - c) in d1 or (r + c) in d2:
12                    continue
13                queens.append(c)
14                cols.add(c); d1.add(r - c); d2.add(r + c)
15                dfs(r + 1)
16                queens.pop()
17                cols.remve(c); d1.remove(r - c); d2.remove(r + c)
18        dfs(0)
19        return res

复杂度：

  • 时间 O(n!)
  • 空间 O(n)

5.2 解数独 | Hard

题目：编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示

思路分析：

每个空格的填数有：行约束、列约束、9宫格约束 我们先预处理记录每个空格位置[r, c]，逐个处理每个空格，用i作为进度指针 在第i个空格[r, c]我们枚举所有数字1～9，每个候选进行三重判断：行、列、9空格，如果都不冲突则填入该数字，然后递归到下一个空格dfs(i + 1)；当i == len(empties)时，所有空格全部填完

方阵特点: 当前位置 [r, c]

  • 行编号即 r,列编号即 c
  • 9空格编号满足：r // 3 * 3 + c // 3

踩坑记录：

  • 先预处理后dfs
  • dfs传递的是处理空格的个数/位置
  • N 皇后要收集全部解，所以 dfs(row + 1) 返回后无条件撤销、继续试下一列。数独只有唯一解，找到就该停

代码：

 1class Solution:
 2    def solveSudoku(self, board: List[List[str]]) -> None:
 3        """
 4        Do not return anything, modify board in-place instead.
 5        """
 6        boxes = [set() for _ in range(9)]
 7        rows  = [set() for _ in range(9)]
 8        cols  = [set() for _ in range(9)]
 9        empties = []
10
11        for r in range(9):
12            for c in range(9):
13                ch = board[r][c]
14                if ch == ".":
15                    empties.append((r, c))
16                else:
17                    b = r // 3 * 3 + c // 3
18                    boxes[b].add(ch)
19                    cols[c].add(ch)
20                    rows[r].add(ch)
21
22        def dfs(i):
23            if i == len(empties):
24                return True
25
26            r, c = empties[i]
27            b = r // 3 * 3 + c // 3
28            for num in "123456789":
29                if num in rows[r] or num in cols[c] or num in boxes[b]:
30                    continue
31                board[r][c] = num
32                boxes[b].add(num); cols[c].add(num); rows[r].add(num)
33                if dfs(i + 1):
34                    return True
35                board[r][c] = "."
36                boxes[b].remove(num); cols[c].remove(num); rows[r].remove(num)
37            return False
38
39        dfs(0)

复杂度：

  • 时间O(1)，实质 O(9^m) 强剪枝
  • 空间O(1)

6 分割型

6.1 分割回文串 | Medium

题目：将字符串 s 分割成若干子串，使每个子串都是回文串。返回所有可能的分割方案 "aab" → [["a","a","b"], ["aa","b"]]

思路分析： start 的语义变了：不再是"下一个元素的下标"，而是"下一段的起点"。本质上是在 n-1 个间隙上做子集型决策

每一刀切出的子串只有一个回文约束。 我们沿字符串从左往右切，用start作为待切子串的左端点，天然必然回头重切也不会产生重复的方案：

  • 在位置start，我们枚举所有右端点[start,...,n - 1]，对每一个候选子串s[start: i + 1]进行是否回文判断，合法加入path，然后递归到下一段dfs(i + 1)，当start == n时，整个串切完，加入最终结果

踩坑记录：

  • 终止条件是start == n

代码：

 1class Solution:
 2    def partition(self, s: str) -> List[List[str]]:
 3        def is_palindrome(l: int, r: int) -> bool:
 4            while l < r:
 5                if s[l] != s[r]:
 6                    return False
 7                r -= 1; l += 1
 8            return True
 9
10        n = len(s)
11        res, path = [], []
12
13        def dfs(start):
14            if start == n:
15                res.append(path[:])
16                return 
17            for i in range(start, n):
18                if not is_palindrome(start, i):
19                    continue
20                path.append(s[start:i + 1])
21                dfs(i + 1)
22                path.pop()
23
24        dfs(0)
25        return res

复杂度：

  • 时间 O(1)
  • 空间 O(1)

6.2 复原 IP 地址 | Medium

题目：有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成

思路分析： 每段IP约束：

  • 数值约束(<=255)
  • 前导零约束：
  • 段长约束：
  • 段数约束：刚好4段

我们沿字符串从左到右切，用start作为待切子串的左端点，天然避免回头重切；在位置start，我们枚举所有段长[1, 2, 3]（该段最多有3个字符，最少有1个），每个候选进行两重判断：前导零和是否>255，如果合法则加入path，当path长度为4以及遍历完所有字符（start == n）时收录为一个解

边界特点：当前段 s[start : start+l]

  • 越界满足：start + l > n → break（l 递增，后面只会更越界）
  • 前导零满足：l > 1 and seg[0] == '0' → continue（单个 "0" 合法）

踩坑记录：

  • return 条件
  • 4个约束

代码：

 1class Solution:
 2    def restoreIpAddresses(self, s: str) -> List[str]:
 3        n = len(s)
 4        res, path = [], []
 5
 6        def dfs(start):
 7            if len(path) == 4:
 8                if start == n:
 9                    res.append(".".join(path))
10                return
11            for l in (1, 2, 3):
12                if start + l > n:
13                    break
14                seg = s[start:start+l]
15                if (l > 1 and seg[0] == "0") or int(seg) > 255: # 前导0/超范围
16                    continue
17                path.append(seg)
18                dfs(start + l)
19                path.pop()
20        dfs(0)
21        return res

复杂度：

  • 时间O(1)
  • 空间O(1)

7 多列表选择型

7.1 电话号码的字母组合 | Medium

题目： 给定按键数字字符串（2-9），返回所有可能的字母组合

2 → "abc"   3 → "def"   4 → "ghi"
5 → "jkl"   6 → "mno"   7 → "pqrs"
8 → "tuv"   9 → "wxyz"

"23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]

思路分析：

  • 每个数字位置是一层，选择列表是该数字对应的字母

踩坑记录：

  • 传递的是处理第几个digits char

代码：

 1class Solution:
 2    def letterCombinations(self, digits: str) -> List[str]:
 3        mapping = {
 4            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
 5            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
 6        }
 7
 8        n = len(digits)
 9        res, path = [], []
10
11        def dfs(idx):
12            if len(path) == n:
13                res.append("".join(path))
14                return  
15            for ch in mapping[digits[idx]]:
16                path.append(ch)
17                dfs(idx + 1)
18                path.pop()
19        dfs(0)
20        return res

复杂度：

  • 时间 O($4^n$)（最多 4 个字母）
  • 空间 O(n)

8 构造生成型

8.1 括号生成 | Medium

题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

思路分析： 不是生成后判断是否合法，而是不合法的选择根据不进入循环

假设当前已经有left个(， right个) 必要条件有：

  • left - right >= 0
  • left <= n
  • right <= n $\Rightarrow$ right <= left <= n

不符合必要条件的一定是思路，但是满足必要条件的不一定是活路

充分条件：给定满足 A、B 的前缀，构造一个补全方案，先把剩下的 ( 全填完，再把剩下的 )

当前:  bal = left - right ≥ 0,  left ≤ n
补 (n-left) 个 "(" → bal 单调上升,恒 ≥ 0 ✓
补 (n-right) 个 ")" → bal 从峰值单调降到 0,中途恒 ≥ 0 ✓
  • 末态 left = right = n，bal = 0，合法。所以任何满足 A、B 的前缀都至少有一个解

踩坑记录：

  • right < left 不要写成 right < n，否则会生成 ()) 这种非法串

代码：

 1class Solution:
 2    def generateParenthesis(self, n: int) -> List[str]:
 3        res, path = [], []
 4
 5        def dfs(left, right):
 6            if len(path) == 2 * n:
 7                res.append("".join(path))
 8                return
 9            if left < n:
10                path.append("(")
11                dfs(left + 1, right)
12                path.pop()
13            if right < left:
14                path.append(")")
15                dfs(left, right + 1)
16                path.pop()
17
18        dfs(0, 0)
19        return res

复杂度：

  • 时间 O(4ⁿ/√n)
  • 空间 O(n)

9 网格搜索型

9.1 单词搜索 | Medium

题目：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路分析： 我们以每个格子为起点各搜一次，用k表示word的字符下标当作进度指针 dfs(r, c, k)表示用board[r][c]匹配word[k]，进入后做越界和字符匹配判断：not (0 <= r < m and 0 <= c < n) or word[k] != borad[r][c]，任一成立返回False，若k已经是最后一位返回True。然后做选择board[r][c] = "#"，递归到四个方向dfs(r+-1, c, k+1) or dfs(r, c+-1, k +1)，最后恢复board[r][c]

踩坑记录：

  • 越界必须靠 or 短路挡在 board[r][c] 求值之前，否则 Python 负索引会绕到末尾，静默取到错误的格子

代码：

 1class Solution:
 2    def exist(self, board: List[List[str]], word: str) -> bool:
 3        m, n = len(board), len(board[0])
 4
 5        def dfs(r, c, k):
 6            if k == len(word):
 7                return True
 8            if not (0 <= r < m and 0 <= c <n) or word[k] != board[r][c]:
 9                return False
10
11            # 注意顺序
12            # if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[k]:
13            #     return False
14            # if k == len(word) - 1:
15            #     return True
16                
17            tmp, board[r][c] = board[r][c], "#"
18            found = dfs(r-1, c, k+1) or dfs(r+1, c, k+1) or dfs(r, c-1, k+1) or dfs(r, c+1, k+1)
19            board[r][c] = tmp
20            return found
21
22        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

复杂度：

  • 时间 O(m · n · 3^L)，L = len(word)
    • m×n 个起点
    • 每个起点第一步 4 个方向，之后每步来路那格已是 '#'，实际只剩 3 个方向 → 3^(L-1)
  • 空间 O(L)：递归栈深度等于词长。原地标记省掉了 visited 数组，无额外辅助空间

10 剪枝与去重

剪枝的写法只有一个位置：for 循环里、append 之前

  1. 可行性剪枝：这个选择本身就不合法，跳过
1if not is_pal(start, end):  continue     # 131
2if int(seg) > 255:          continue     # 93
3if c in cols:               continue     # 51
  1. 排序 + break（break vs continue）
1if candidates[i] + total > target:  break          # 39/40/216：已排序，后面只会更大

break 的前提是已排序。没排序只能 continue，剪枝效果差一个量级。这是回溯题里"先排序"最重要的两个理由之一（另一个是去重）

  1. 数量剪枝
1for i in range(start, n - (k - len(path)) + 2):   # 77

剩下的元素凑不满 k 个，整棵子树就没必要进

  1. 去重剪枝：同层 vs 同枝（本章最容易错的一节） ![[14-dedup.svg]]

前提：必须先 sort()，让重复元素相邻，判断才成立。

  • 组合 / 子集型（40、90）用 start：
1if i > start and nums[i] == nums[i - 1]:
2    continue

i > start 就等价于"不是本层的第一个"。简单直观。

  • 排列型（47）用 used：
1if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
2    continue                             # ✓ 同层去重，推荐

怎么理解 not used[i-1]？used[i-1] == False 有两种可能：① 还没轮到它；② 刚被撤销回来。而在同一层的 for 循环里只可能是 ②，说明 nums[i-1] 是本层的兄弟分支刚试过的，那么和它相等的 nums[i] 就该跳过。

写成 used[i-1]（同枝去重）也能 AC，但慢很多：它是在子树内部才发现重复，剪得晚。面试里能说清这一点，比背对写法更有价值。

为什么只剪兄弟、不剪父子：图里那两条绿色的边[1] → [1,1] 用的正是第二个 1，这是同枝方向，完全合法。剪掉就会漏掉 [1,1,2] 这类解。

  1. 状态判重加速

51 的三个集合、37 的三组 9×9 布尔数组，本质都是用空间把 O(n) 的冲突检查降到 O(1)。回溯题里"每个节点的处理代价"经常被忽略，但它直接乘在总复杂度上

  1. 原地标记与恢复现场

79 的 board[r][c] = '#'。适用条件：状态天然存在于输入结构里，且能安全地写回去。省掉了额外的 visited 数组

  1. 记忆化剪枝

当"不同分支会走到完全相同的子问题"时，回溯可以叠加记忆化。140 单词拆分 II 就是典型：以 start 为键缓存"从 start 开始的所有拆分方案"