06 · 回溯与分支限界（Backtracking & Branch and Bound）

📅 预计 90 分钟　|　⭐ 本章主题：用「试错 + 撤销」穷举解空间，靠剪枝把不可能的分支提前砍掉

6.0 从走迷宫说起

想象你在走一座巨大的迷宫：每个岔路口选一条路走进去，走到死胡同就原路退回，换下一个路口再试。这个「往前走、走不通就退回上一个路口换方向」的过程，就是回溯（backtracking）最直观的样子。

计算机里的很多问题没有现成公式可以一步算出答案，比如「把 8 个皇后摆到棋盘上让它们互不攻击」「从一堆数字里选出和为某个值的组合」。这类问题的共同点是：答案空间有限但巨大，每个位置有几种选择，选择连起来就像一棵不断分叉的树。回溯法要做的，就是把这棵树上的每条路都走一遍，走到明显没希望的分支就提前回头。

先记住直觉上的三个关键词：选择 → 递归 → 撤销。后面所有代码都是这个模板的变体。

6.1 解空间树

把每个「选择」画成一棵树

解空间树（solution space tree）是回溯法的地图：树根是「还没做任何决定」的状态，每个节点代表「做了前面几个决定后的状态」，从根到叶的每条路径对应一个完整候选解。

例如一个长度为 n 的 0/1 序列，每一位可选 0 或 1。n=3 时解空间就是一棵满二叉树，共 2³ = 8 片叶子。

def all_binary_strings(n):
    result = []

    def backtrack(i, path):
        if i == n:                # 决定做完了，记录一个完整解
            result.append(path)
            return
        backtrack(i + 1, path + "0")   # 分叉一：这一位选 0
        backtrack(i + 1, path + "1")   # 分叉二：这一位选 1

    backtrack(0, "")
    return result

print(all_binary_strings(3))
# 输出: ['000', '001', '010', '011', '100', '101', '110', '111']

注意这里没有「撤销」步骤，因为 path + "0" 每次生成新字符串，不修改旧值。若你用的是同一个可变容器（比如列表）来存路径，就必须在递归返回后把刚加的元素删掉——这就是「撤销」的由来。

⚠️ 常见错误

分不清「拷贝」和「引用」：记录结果写 result.append(path) 而不是 path[:]，后面 path.pop() 会把已记录的解一并改掉，最终所有结果都一样。
忘了撤销：用共享列表做路径但递归后不 pop()，上一层的选择会残留到下一层。
把解空间树和答案混淆：解空间树是「所有可能的路径」，答案只是其中满足约束的那几条；剪枝发生在树上，不是等树长完再筛。

6.2 回溯法通用框架

三条固定动作：选、探、撤

回溯法的代码几乎长一个样，三件套：

选（choose）：在当前状态选择一个候选；
探（explore）：带着这个选择递归下去；
撤（unmake）：撤销选择，回到选择前的状态，试下一个候选。

一个比 0/1 序列更贴近真实回溯的经典例子——生成 n 对合法括号：

def generate_parenthesis(n):
    result = []

    def backtrack(left, right, path):
        if len(path) == 2 * n:        # 括号用完，得到一个合法解
            result.append(path)
            return
        if left < n:                  # 还能放左括号
            backtrack(left + 1, right, path + "(")
        if right < left:              # 右括号不能超过左括号（剪枝！）
            backtrack(left, right + 1, path + ")")

    backtrack(0, 0, "")
    return result

print(generate_parenthesis(2))
# 输出: ['(())', '()()']
print(generate_parenthesis(3))
# 输出: ['((()))', '(()())', '(())()', '()(())', '()()()']

这里的 if right < left 就是剪枝（pruning）：一旦当前路径的右括号比左括号多，这个分支无论怎么走都不可能是合法括号串，直接不展开。剪枝是回溯法性能的关键——它把「全部枚举」变成「枚举 + 排除」。

回溯法的时间复杂度通常是「节点数 × 每节点成本」。没有剪枝的 n 位 0/1 枚举是 O(2ⁿ)，八皇后约 O(n!)，全排列是 O(n·n!)。剪枝不改变最坏复杂度，但能大幅削减平均情况下的搜索量。

⚠️ 常见错误

剪枝条件边界写错：如右括号判断写成 right < n，会生成一堆非法括号串。
结束条件和剪枝混为一谈：结束条件是「得到一个完整解」；剪枝是「提前知道这条路不可能有解」。
没考虑重复选择：同一层两个分支可能产生同一解（如全排列里有两个相同数字），需要额外的 used 标记或排序去重。

6.3 八皇后问题 ⭐

给每行安排一个「互不攻击」的列

八皇后（N-Queens）：在 n×n 棋盘放 n 个皇后，任意两个不能在同一行、同一列、同一对角线上。解法按行逐行放：在第 row 行尝试每个列，若与前面已放的皇后都不冲突，就放下去，再递归下一行。

def solve_n_queens(n):
    result = []
    board = [-1] * n          # board[row] = col，记录每行皇后的列位置

    def is_safe(row, col):
        for r in range(row):  # 只检查已经放好的行
            same_col = board[r] == col
            same_diag = abs(board[r] - col) == abs(r - row)   # 行差等于列差 → 在同一斜线
            if same_col or same_diag:
                return False
        return True

    def backtrack(row):
        if row == n:              # n 行全放完
            result.append(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

print(len(solve_n_queens(4)))   # 输出: 2    四皇后 2 种摆法
print(len(solve_n_queens(8)))   # 输出: 92   八皇后 92 种摆法

两个细节值得记：

对角线判断：两格在同一斜线上，当且仅当「行差绝对值 == 列差绝对值」。
按行放置天然消掉了「同行」约束，冲突检查只需看列和对角线。

n 皇后的放置方式数量随 n 快速爆炸（8 皇后 92 种，10 皇后 724 种），这正是「暴力 + 剪枝」的典型画像——剪枝对八皇后尤其有效，因为大部分列位置在早期就会被排除。

⚠️ 常见错误

对角线判断写错：用 == 而没加绝对值，或把条件写成两倍/一半关系，斜线会漏判。
结果没拷贝：result.append(board)，后面行被覆盖，所有记录变成同一个终态。
列号从 1 开始：若把列号写成 1..n，数组下标和比较全乱套。

6.4 子集和问题

从一堆数里挑出和为 target 的组合

子集和（subset sum）：给定一串正整数，找出所有和为 target 的子集（每个数最多用一次）。搜索树上每个节点决定「当前这个数选 or 不选」，走到和为 target 就记下。

def subset_sum(nums, target):
    result, path = [], []

    def backtrack(start, cur_sum):
        if cur_sum == target:
            result.append(path[:])
            return
        if cur_sum > target or start >= len(nums):
            return                # 剪枝：超了或没数可用了
        for i in range(start, len(nums)):
            path.append(nums[i])               # 选
            backtrack(i + 1, cur_sum + nums[i])   # 探：下个数从 i+1 开始，避免重复组合
            path.pop()                         # 撤

    backtrack(0, 0)
    return result

print(subset_sum([1, 2, 3, 4], 6))
# 输出: [[1, 2, 3], [2, 4]]
print(subset_sum([2, 3, 5], 8))
# 输出: [[3, 5]]

要点：for i in range(start, ...) 的 start 参数保证组合不重不漏——选过的数不会再被回头选，避免出现 [1,2,3] 和 [1,3,2] 这样顺序不同但内容相同的重复解。

若题目要求子集可以重复使用某个数，把递归参数改成 backtrack(i, ...)（不 +1）即可。

⚠️ 常见错误

start 忘递增：backtrack(i, ...) 或 backtrack(start, ...) 会导致重复组合或无限递归。
剪枝只适用于全正数：数据里有负数时，超了也可能再加负数回来，cur_sum > target 的剪枝失效。
找到解后没有 return：继续往下走会产出 [1, 2, 3, ...] 这种包含已找到解的超集。

6.5 全排列

给 n 个元素排顺序，穷举所有排列

全排列（permutation）：把给定数组的所有排列都列出来。与子集和不同，这里每个元素都必须用上、顺序敏感，所以需要一个 used 标记哪些元素已经放进当前路径。

def permute(nums):
    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
            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 个不同元素的全排列是 n! 个。3 个是 6，4 个是 24，8 个就到 40320 了。所以全排列类题目，n 通常很小（一般 ≤ 8~10）。

若输入里有重复元素，比如 [1, 1, 2]，上面的代码会输出重复排列。去重标准套路：先排序，然后同一层里跳过与上一个相同的数。原理：让相等的数字之间只有一种被选顺序。

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]]

⚠️ 常见错误

忘用 used：全排列要求每个元素恰好出现一次；不用 used 会无限递归。
去重剪枝条件写反：not used[i - 1] 和 used[i - 1] 是两种等价写法，写反会导致去重失败或错误地跳过所有重复。
把排列当组合写：排列强调顺序（[1,2] ≠ [2,1]），组合不强调（{1,2} = {2,1}），两者的 start/used 写法不能混用。

6.6 分支限界思想

从「深度优先试错」到「按上界排队」

回溯法本质是深度优先搜索解空间树：一条路走到黑，失败再回头。分支限界法（branch and bound）换了个思路：用广度优先（或优先队列）展开节点，并且每个节点带一个界限值（bound）——预测从该节点出发能拿到的最好结果。若某节点的上界比已知的可行解还差，就把它整个分支剪掉。

以 0-1 背包为例：给定重量和价值，选若干物品装进容量为 C 的背包使价值最大。物品按「单位价值（价值/重量）」降序排列后，从当前节点继续做乐观估计：把剩余容量全用来装「剩下的最贵的物品」（允许拆分成碎片来估算），得到一个上界。若上界 ≤ 当前已知最优价值，这个分支不可能产出更好的解，直接砍掉。

from collections import deque

def knapsack_bnb(weights, values, capacity):
    n = len(weights)
    # 按单位价值从高到低排序，让上界估计更紧
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    w = [it[0] for it in items]
    v = [it[1] for it in items]

    def bound(i, cur_w, cur_v):
        """乐观上界：剩余容量全按单位价值最高的物品估算（允许拆分）"""
        total_v, cap = cur_v, capacity - cur_w
        for j in range(i, n):
            if cap >= w[j]:
                total_v, cap = total_v + v[j], cap - w[j]
            else:
                return total_v + v[j] * cap / w[j]
        return total_v

    best = 0
    q = deque([(0, 0, 0)])      # (下一个要决定的物品下标, 当前重量, 当前价值)
    while q:
        i, cur_w, cur_v = q.popleft()
        best = max(best, cur_v)
        if i == n:
            continue
        # 分支一：装当前物品（先看是否超重、上界是否值得）
        if cur_w + w[i] <= capacity and bound(i + 1, cur_w + w[i], cur_v + v[i]) > best:
            q.append((i + 1, cur_w + w[i], cur_v + v[i]))
        # 分支二：不装当前物品
        if bound(i + 1, cur_w, cur_v) > best:
            q.append((i + 1, cur_w, cur_v))
    return best

print(knapsack_bnb([2, 3, 4], [3, 4, 5], 6))
# 输出: 8   选重量 2 和 4，价值 3 + 5

bound 函数算的是一个「做梦」的最大值——假设剩余容量可以装任意碎片，显然真实解不可能超过它。所以「上界 ≤ 当前最优」意味着该分支无望，剪掉它不会丢解。

⚠️ 常见错误

上界算得太松：如果 bound 直接把所有剩余物品全算上（不管容量），剪枝形同虚设。
剪枝条件方向写反：是 bound(...) > best 才保留，写成 < 会剪掉所有分支。
排序改了物品顺序却忘了对应价值：重量、价值必须一起排序，否则上界算错。
把分支限界当成 DP：分支限界仍是搜索，最坏复杂度可能仍是 O(2ⁿ)；DP 才是多项式。n 小、剪枝有效时用分支限界，n 大时应优先想 DP。

6.7 回溯 vs 分支限界

维度	回溯法	分支限界法
搜索策略	深度优先（DFS）	广度优先 / 优先队列
核心机制	试错 + 撤销	界限函数 + 剪枝
剪枝依据	约束条件（不合法就停）	界限值（不可能更优就停）
找解方式	一路找，先到先得	依界限排队，逐步逼近最优
典型问题	八皇后、子集和、全排列、图着色	0-1 背包、旅行商（TSP）
目标	找一个或所有可行解	通常是求最优解

一句话：回溯适合「问有没有/有几个解」，分支限界适合「问最优解是多少」。两者都建立在解空间树上，区别在「怎么走」和「凭什么剪」。

🧠 记忆口诀

回溯三件套：选、探、撤——选了就递归，回来就撤销。
剪枝两句话：不合法就停（约束剪枝），没希望就砍（界限剪枝）。
八皇后看对角线：行差 = 列差，就在一条斜线。
组合用 start，排列用 used，重复元素先排序再同级去重。

⭐ 考点清单

解空间树的概念：节点、分支、叶子与候选解的关系
回溯模板：选择 → 递归 → 撤销；共享路径必须拷贝记录
八皇后：按行放置、is_safe 的列与对角线判断、剪枝收益
子集和：start 参数去重、全正数剪枝、找解后 return
全排列：used 标记、n! 数量级、重复元素去重写法
分支限界：上界函数的含义、bound > best 才保留
回溯 vs 分支限界：DFS vs BFS、约束剪枝 vs 界限剪枝
复杂度认知：枚举 O(2ⁿ)/O(n!)，剪枝改善平均不改善最坏

📌 中英术语表

中文	English	说明
回溯法	backtracking	深度优先试错 + 撤销
解空间树	solution space tree	所有候选解构成的分叉结构
剪枝	pruning	提前排除不可能的分支
约束	constraint	解必须满足的限制条件
可行解	feasible solution	满足约束的解
最优解	optimal solution	所有可行解里最好的
上界	upper bound	某分支可达到结果的天花板
分支限界	branch and bound	用界限值剪枝的最优化搜索
搜索树	search tree	搜索过程展开的树
0-1 背包	0-1 knapsack	物品只能整体取或不取
单位价值	unit value	价值 / 重量
排列	permutation	顺序有关，用 used 去重
组合	combination	顺序无关，用 start 去重
深度优先搜索	depth-first search	一路走到底再回头
撤销	unmake	恢复选择前的状态