第 12 章：分治与回溯
元数据卡
| 属性 | 值 |
|---|---|
| 难度 | （巅峰型） |
| 前置 | 递归、数组操作、第 9-10 章（排序）、第 11 章（搜索） |
| 关键词 | 分治三步法·最大子数组·逆序对·回溯三要素·选择·约束·目标·N皇后·全排列·子集·子集和·剪枝·状态树 |
| 预计阅读 | 120 分钟 |
| 代码行 | ~200 行（三语言合计） |
你在哪
你学到的大部分方法都有一个共同模式——把大问题拆成小问题，解决小问题，组合起来。但当拆到最小发现走不通时，你需要"回到上一个岔路口重新选"——这就是回溯。
前 11 章你一直在处理确定性的问题——排序、搜索、哈希、树。这些问题有一个共同的特点：你可以用算法推导出唯一的正确答案。
现在我们要面对更复杂的局面：
在一个数组中找一个连续子数组，使其和最大。你可以枚举所有 O(n²) 个子数组，但能不能更快？
在一个 8×8 的棋盘上放 8 个皇后，使它们互不攻击。有多少种放法？怎么用代码找到所有放法？
给定一个集合
[1,2,3]，列出它的所有子集。一共 8 个，但你怎么确保不遗漏、不重复？
这些问题没有「一个算法 → 刷一下出结果」那么简单。它们需要你系统地生成所有可能性，或者巧妙地分而治之。
分治和回溯是两种最基础也最强大的算法设计范式。分治是「把大问题变成小问题，小规模解决了再组合」。回溯是「试错——走不通就回头」。理解它们，不仅是通往动态规划（下一章）的桥梁，更是你从「算法的使用者」变成「算法的设计者」的关键一步。
你的任务
本章分层
- 必读：分治三步法（分-治-合）——用 1-2 个例子（如最大子数组）说明模板；回溯三要素（选择-约束-目标）——用 N 皇后或全排列一个例子说清楚
- 选读：逆序对统计（归并排序的扩展应用）；子集生成的
start指针技巧- 深水区：子集和的剪枝优化（排序+break+同层去重）；分治、回溯、动态规划的边界区分
本章不会要求你掌握
- 所有回溯题型的完整代码（用 2 个例子讲懂模板即可，不要堆题）
- DP 对比——只需保留一句"有重叠子问题时再考虑 DP"
读完本章，你应当能：
- 用分治三步法分析问题（分-治-合）
- 实现最大子数组问题的分治解法
- 画出回溯算法的决策树，套用模板
- 用回溯模板解决 N 皇后或全排列
- 区分分治、回溯、动态规划的基本区别
遭遇战→获得技能
① 分治（Divide & Conquer）—— 三步解决复杂问题
核心直觉：如果原问题很难，把它切成更小的相同问题。小到能直接解决时再组合回去。
这就是分治的法典：
- 分（Divide）：将问题分解为若干子问题
- 治（Conquer）：递归地解决每个子问题（当问题足够小时直接求解）
- 合（Combine）：将子问题的解组合成原问题的解
你其实已经见过分治了——第 9 章的归并排序就是它的完美范例。现在我们用这个框架解决两个经典问题。
1.1 最大子数组问题（Maximum Subarray）
问题：给定整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
暴力法 O(n²)——枚举每个起点终点。分治法把这个复杂度拉到 O(n log n)。
分治分析
分：从中点切开 → 左边问题 + 右边问题
治：递归求左右的最大子数组
合：还有第三种可能——跨越中点的子数组
答案 = max(左最大, 右最大, 跨中点最大)def max_subarray_divide_conquer(nums):
"""分治求最大子数组和"""
def helper(left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
# 治：递归求左右
left_max = helper(left, mid)
right_max = helper(mid + 1, right)
# 合：计算跨中点的最大和
# 从中点向左扩展
left_sum = float('-inf')
cur_sum = 0
for i in range(mid, left - 1, -1):
cur_sum += nums[i]
left_sum = max(left_sum, cur_sum)
# 从中点向右扩展
right_sum = float('-inf')
cur_sum = 0
for i in range(mid + 1, right + 1):
cur_sum += nums[i]
right_sum = max(right_sum, cur_sum)
cross_sum = left_sum + right_sum
return max(left_max, right_max, cross_sum)
return helper(0, len(nums) - 1)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_divide_conquer(nums)) # → 6 (子数组 [4, -1, 2, 1])为什么跨中点一定包含 mid 和 mid+1？
因为「最大子数组」是连续的。如果它在左半没有延伸到 mid，它就完全属于「左子问题」的范围，会被递归解决。跨中点的定义就是「至少包含 mid 和 mid+1 各一个元素」的连续数组。所以跨中点方案只需要从中点左右扩展，不需要枚举所有可能。
但是等等——最大子数组明明有 O(n) 的 Kadane 算法，为什么还要学分治？
你说得对。Kadane 算法（动态规划）O(n) 就能解决最大子数组问题。学这个分治版本不是为了解决这个问题，而是为了理解分治思维。最大子数组的分治解法让你看到：即使是一个看似「必须连续扫描」的问题，分治法也能给出一个完全不同的视角——而同一个结构在「逆序对」问题上威力更大。
** Java 差异：** 注意 Java 没有内置的
float('-inf')，你需要Integer.MIN_VALUE。而且递归深度可能造成栈溢出（StackOverflowError），所以真正的工业代码要么用迭代，要么显式增大栈大小。
1.2 逆序对（Count Inversions）—— 归并排序的探针
问题：给定数组
[2, 4, 1, 3, 5]，计算有多少对(i, j)满足i < j且nums[i] > nums[j]。上例中：
(2,1), (4,1), (4,3)→ 共 3 对。
暴力法是 O(n²)，分治能到 O(n log n)。关键洞察：在归并排序的合并过程中，当左半的元素大于右半的元素时，左半剩余的所有元素都和这个右半元素构成逆序对。
def count_inversions(nums):
"""归并排序同时统计逆序对"""
def merge_sort_and_count(arr, temp, left, right):
if left >= right:
return 0
mid = (left + right) // 2
count = 0
# 左右递归统计
count += merge_sort_and_count(arr, temp, left, mid)
count += merge_sort_and_count(arr, temp, mid + 1, right)
# 合并并统计跨中点的逆序对
i = left # 左半指针
j = mid + 1 # 右半指针
k = left # temp 数组指针
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
# arr[i..mid] 所有元素都 > arr[j]
# 它们都和 arr[j] 构成逆序对
count += (mid - i + 1)
temp[k] = arr[j]
j += 1
k += 1
# 收尾
while i <= mid:
temp[k] = arr[i]
i += 1
k += 1
while j <= right:
temp[k] = arr[j]
j += 1
k += 1
# 拷贝回原数组
for i in range(left, right + 1):
arr[i] = temp[i]
return count
n = len(nums)
temp = [0] * n
return merge_sort_and_count(nums, temp, 0, n - 1)
nums = [2, 4, 1, 3, 5]
print(count_inversions(nums)) # → 3
# 原始数组已被修改为排序后的版本
print(nums) # → [1, 2, 3, 4, 5]关键行讲解
count += (mid - i + 1)这里的神奇之处：当 arr[j] < arr[i] 时，因为左右两半各自有序，arr[i..mid] 全部大于 arr[j]。这意味着 arr[j] 和左半所有未处理的元素都构成逆序对，一共 mid - i + 1 个。
不用排序，只计数也能做
如果你的需求是只统计逆序对数量而不修改原数组，可以在递归时拷贝一份：
def count_inversions_pure(nums):
"""纯计数版——不改变原数组"""
n = len(nums)
if n <= 1:
return 0
mid = n // 2
left = nums[:mid]
right = nums[mid:]
count = count_inversions_pure(left) + count_inversions_pure(right)
# 合并计数
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
count += len(left) - i # 这里和上面一样
k += 1
nums[k:] = left[i:] + right[j:]
return count② 回溯（Backtracking）—— 系统的试错哲学
核心直觉：有路就走，走不通就回头。
回溯是暴力搜索的「优雅」版本。它的工作量本质上和暴力没区别，但它有两件事做得更好：
- 不生成无效的中间状态（剪枝）
- 系统性地遍历所有可能性（不会漏也不会重复）
回溯的代码框架极其固定，因为所有回溯问题共享同一个灵魂：
def backtrack(路径, 选择列表):
if 满足终止条件: # 目标
result.append(路径)
return
for 选择 in 选择列表:
if 不满足约束条件: # 约束/剪枝
continue
做选择 # 路径.append(选择)
backtrack(新路径, 新选择列表) # 递归
撤销选择 # 路径.pop()这就是回溯三要素：选择、约束、目标。
| 要素 | 含义 | 在 N 皇后中的例子 |
|---|---|---|
| 选择 | 每步有几种选项 | 当前行在哪一列放皇后 |
| 约束 | 什么选择是非法的 | 不能和已有皇后冲突 |
| 目标 | 什么时候找到了解 | 8 行都放了皇后 |
2.1 N 皇后 —— 回溯的「hello world」
问题：在 N×N 的棋盘上放 N 个皇后，任何两个皇后不能在同一行、同一列、同一对角线。
核心思路：一行一行放。放第 i 行时，检查第 i 行的每列是否是合法位置（约束检查），如果是就放下去然后递归下一行。
def solve_n_queens(n):
"""N 皇后问题——返回所有合法棋盘"""
result = []
# 用一维数组 board[row] = col 表示棋盘
board = [-1] * n
def is_safe(row, col):
"""检查 (row, col) 是否安全"""
for r in range(row):
c = board[r]
# 同列冲突 或 对角冲突
if c == col or abs(r - row) == abs(c - col):
return False
return True
def backtrack(row):
if row == n: # 目标：所有行都放了皇后
result.append(
["." * col + "Q" + "." * (n - col - 1) for col in board]
)
return
for col in range(n): # 选择：尝试当前行每一列
if is_safe(row, col): # 约束剪枝
board[row] = col # 做选择
backtrack(row + 1) # 递归
board[row] = -1 # 撤销选择
backtrack(0)
return result
solutions = solve_n_queens(4)
print(f"4 皇后的解数量: {len(solutions)}") # → 2
for sol in solutions:
for row in sol:
print(row)
print()
# .Q..
# ...Q
# Q...
# ..Q.
#
# ..Q.
# Q...
# ...Q
# .Q..为什么用一维数组？ 因为每行只有一个皇后，这是天然的约束约束。用 board[row] = col 比二维布尔数组更简洁、更高效。
对角线冲突检测 abs(r - row) == abs(c - col)
两条对角线：主对角线（左上-右下）满足 row - col 为常数；副对角线（左下-右上）满足 row + col 为常数。用 abs(r - row) == abs(c - col) 可以同时检查两种对角线——两个点在同一条对角线上当且仅当行差等于列差。
** Java 差异：** Java 的
List<List<String>>类型声明又臭又长。同样逻辑的 Java 代码会比 Python 长两倍。但核心逻辑一模一样——只是语法噪音多了。
2.2 全排列 —— 排列 vs 组合的分水岭
问题：给定
nums = [1, 2, 3]，返回所有可能的排列。
全排列的特点是顺序重要——[1, 2, 3] 和 [1, 3, 2] 是两个不同的排列。因此每步选择的约束是：当前路径中没出现过的元素。
def permute(nums):
"""全排列——回溯标准模板"""
result = []
path = []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums): # 目标
result.append(path[:]) # path[:] 拷贝，防止后续修改
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]))
# → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]状态树可视化（n=3）
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] ... 等 6 个叶子节点全排列的去重版本（nums 包含重复元素时）
def permute_unique(nums):
"""含重复元素的全排列——去重剪枝"""
nums.sort() # 先排序，让相同元素相邻
result = []
path = []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 剪枝：当前元素和前一个相同，且前一个还没用过
# → 跳过。这保证相同元素的相对位置固定
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]))
# → [[1,1,2], [1,2,1], [2,1,1]]去重剪枝的灵魂一笔：if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]。这条规则的意思是：「当相同元素出现时，只有前一个被用了，后一个才能用。」这样就避免了相同元素在不同顺序下的重复排列。
2.3 子集（Subsets）—— 每个元素「选或不选」
问题：给定
nums = [1, 2, 3]，返回所有子集（共 2^n 个）。
全排列和子集的最大区别：子集关心「有没有」不关心「顺序」。
全排列: [1,2] 和 [2,1] 都算
子集: [1,2] 和 [2,1] 算同一个——所以只产生一个解决方法：每次只从当前元素后面选择，不走回头路。
def subsets(nums):
"""子集生成——每个元素选或不选"""
result = []
path = []
def backtrack(start):
# 每个路径都是合法子集（不设长度约束）
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1) # 关键：只从后面选
path.pop()
backtrack(0)
return result
print(subsets([1, 2, 3]))
# → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]对比：子集 vs 全排列的回溯模板
全排列：used[] 数组 → 选过的不能再选（顺序重要）
子集： start 指针 → 只从当前后面选（顺序不重要）这个 start 指针是回溯中极其重要的一个模式。它意味着「不考虑之前已经处理过的元素」，是「组合类」问题（子集、组合、子集和）的标准写法。
** C++ 差异：** C++ 的
vector::push_back/pop_back就是标准回溯操作。注意result.push_back(path)要做拷贝：result.push_back(path)自动深拷贝，但如果你存的是指针就得手动reserve避免多次分配。
2.4 子集和（Subset Sum）—— 剪枝才是灵魂
问题：给定数组
nums和目标值target，找出所有和为 target 的子集（组合，不可重复使用同一元素）。
def subset_sum(nums, target):
"""子集和——组合求和，每个元素只用一次"""
nums.sort() # 排序：便于剪枝 + 去重
result = []
path = []
def backtrack(start, remaining):
if remaining == 0: # 目标：和等于 target
result.append(path[:])
return
for i in range(start, len(nums)):
# 剪枝 1：当前元素太大 → 后续更大，直接 break
if nums[i] > remaining:
break
# 剪枝 2：同层重复元素去重
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1, remaining - nums[i])
path.pop()
backtrack(0, target)
return result
print(subset_sum([10, 1, 2, 7, 6, 1, 5], 8))
# → [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]剪枝分析
- 排序 + break：因为数组已排序，当前
nums[i] > remaining时，后面的元素更大，更不可能满足条件。直接 break 整层。 - 同层去重：同一递归层中，相同的元素如果已经用第一个试过了，跳过后面的。这避免了
[1, 2, 5]因为有两个 1 而出现两次（[1a,2,5]和[1b,2,5]）。
子集和的可重用版本（每个元素可无限次使用）
def subset_sum_unlimited(nums, target):
"""元素可重复使用的子集和"""
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining:
break
path.append(nums[i])
backtrack(i, remaining - nums[i]) # 注意：i，不是 i+1
path.pop()
backtrack(0, target)
return result
print(subset_sum_unlimited([2, 3, 6, 7], 7))
# → [[2, 2, 3], [7]]可重用的版本传 i 而非 i+1，因为当前元素可以再用一次。
常见陷阱
分治的核心：子问题必须独立
分治不是「递归」的同义词。分治要求子问题之间不重叠。
归并排序的子问题是独立的——左右两半互不相干。最大子数组的子问题部分重叠——左右最大子数组与跨中点最大子数组有重叠，但我们在「合」的步骤中额外处理了这个重叠。
如果子问题高度重叠——比如斐波那契数列——分治会退化到指数级。这正是下一章动态规划出场的原因。
回溯的复杂度
| 问题 | 状态数 | 剪枝后 |
|---|---|---|
| N 皇后（无剪枝） | n! | 远小于 n! |
| 全排列 | n! | n!（无法剪，必须全生成） |
| 子集 | 2^n | 2^n |
| 子集和 | 2^n | 取决于数据 |
回溯的复杂度通常是指数级的。这不是 bug——这是回溯的本质：系统性地枚举所有可能。 剪枝能大幅度加速，但不改变最坏情况的复杂度。
分治 vs 回溯 vs 动态规划（一句话）
- 分治：大问题切成小问题，子问题独立求解再合并
- 回溯：系统性地试所有可能路径，走不通就回头
- 有重叠子问题时再考虑动态规划：把子问题答案存起来避免重复计算
通关挑战
- 分治求多数元素：给定数组，找出出现次数超过一半的元素（LeetCode 169）。尝试分治解法——这也 O(n log n)，但更巧妙
- 数独求解器：用回溯实现 9×9 数独求解器。剪枝的关键是：每填一个格子，只尝试当前行/列/宫格中可行的数字
- 排列的字典序下一个：不生成所有排列，直接给出当前排列的下一个字典序排列（LeetCode 31）
- 组合总和 IV：给你一个无重复的正整数数组和一个 target，求出元素和等于 target 的排列数（注意：不同顺序算不同结果）。这个题归回溯还是 DP？
- N 皇后 bitset 优化：用位运算（三个整数分别表示列、主对角线、副对角线的占用）把 is_safe 的 O(n) 检查降到 O(1)
验收标准
- [ ] 能徒手写出分治三步法解决最大子数组问题
- [ ] 能解释逆序对计数为什么在
else分支做mid - i + 1 - [ ] 能给任意回溯问题套模板：选择、约束、目标三要素
- [ ] 能手写 N 皇后并回答 why 一维数组
- [ ] 能区分全排列（used[]）和子集（start）的回溯写法差异
- [ ] 能画出 n=3 的全排列回溯树
常见卡点
| 卡点 | 破解 |
|---|---|
| 分治的「合」不知道怎么写 | 「合」不是玄学——想想跨中点的方案怎么做就行了。最大子数组问题里是「从中点左右扩展」 |
逆序对的 mid - i + 1 为什么对 | 因为左半已经有序了。arr[i] > arr[j] 意味着左半从 i 开始的每个元素都 > arr[j]——别忘了左半是递增的 |
| 回溯的撤销总是忘 | 模板写熟练：「做选择 → 递归 → 撤销选择」三行紧贴，先背下来再理解 |
| 全排列的 used 数组什么时候恢复 | 递归返回后立刻恢复。 used[i] = True + backtrack + path.pop + used[i] = False |
子集的 path[:] 拷贝 | 不拷贝的话最后 result 里全是同一个 []——因为 path 是引用，后续的 pop 会清空它 |
| 剪枝写得过头导致漏解 | 先写无剪枝版本，再逐层优化。剪枝 = 仍保证正确性的优化 |
现在不需要理解
- 分支限界法（Branch and Bound）—— 回溯 + 上下界估计，在组合优化问题上（TSP、背包）更高效。它比回溯多了「评估当前路径的理论最优值，如果不如已有解就放弃」这一步。
- 分治的 Master Theorem—— 形如 T(n) = aT(n/b) + f(n) 的递归式有通用的复杂度计算公式。知道它但不用死记，因为实际分析时画递归树更直观。
- Meet in the Middle—— 当 2^n 太大但又想用搜索时，把集合平分，分别搜索再合并。这是个比回溯更少的回路的技巧。
旅人笔记
- 分治是「分而治之」思想的完整实践。 就算你忘了所有分治算法，记住「大问题切小问题，小问题独立解决再合并」这个思维框架也值了。
- 逆序对问题是分治最漂亮的「附加价值」案例。 做排序的同时顺手统计了逆序数——如果你在面试中遇到「计算右侧小于当前元素的个数」，这就是逆序对的变种。
- 回溯的撤销操作是大多数 bug 的来源。 每写一个 backtrack，立即写相应的撤销代码。不要先写十个节点再来补撤销——一定会漏。
- N 皇后是全排列的约束版本。 理解了 N 皇后是「全排列 + 对角线约束」，你就看透了回溯的本质：选择 + 约束 + 目标。
- 剪枝不是优化，是灵魂。 没有剪枝的回溯只是慢一点的暴力枚举。剪枝让回溯从一个「理论算法」变成一个「面对现实数据的可用方案」。
一句话记住本章：「分治切到单，回溯记三选，剪枝是关键。」
→ 下一站预告
准备好了吗？如果你觉得分治和回溯已经够复杂了——那下一章会让你真正紧张起来。
第 13 章：动态规划。
这是整个数据结构与算法卷的巅峰之章。你会学到：
- 从递归 → 记忆化搜索 → DP 表格的完整推导过程
- 0-1 背包、完全背包、多重背包
- 最长上升子序列（LIS）、最长公共子序列（LCS）
- 区间 DP、状态压缩 DP
分治和回溯只是热身。动态规划才是真正的 Boss。