第 69 课 - 回溯法基础

所属模块：回溯与搜索难度：中级标签：backtracking, choice, constraint, goal 上一课：贪心正确性证明 下一课：N 皇后问题

学习目标

完成本课学习后，你将能够：

理解回溯法的核心思想：知道什么是回溯，以及它与暴力枚举的本质区别。
掌握回溯法的基本框架：能够描述出回溯算法的通用结构，包括路径、选择列表和约束条件。
使用回溯法解决基础问题：能够用代码实现全排列、子集生成等经典回溯问题。
了解回溯法与其他算法的区别：理解回溯法与深度优先搜索（DFS）、递归的联系与区别。

核心概念

想象你在一个迷宫里寻找宝藏。你从一个岔路口开始，面前有几条路（选择）。你选择一条路走下去，如果遇到死胡同或者确定此路不通（违反约束），就退回到上一个岔路口（回溯），尝试另一条路。如果走到了宝藏所在地（达到目标），就记录下这条路径。这个“尝试-前进-后退-再尝试”的过程，就是回溯法。

回溯法是一种通过探索所有可能的候选解来找出所有解（或一个解）的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃它，即“回溯”并尝试其他可能性。

它的核心要素有三个：

路径 (Path)：你已经做出的选择。
选择列表 (Choices)：当前可以做的选择。
结束条件 (Constraint / Goal)：即判断是否满足条件，是递归的终止条件，通常意味着找到了一个解或路径已无效。

回溯算法的模板就像一个决策树的遍历过程。

# 回溯算法通用框架 (伪代码)
def backtrack(路径, 选择列表):
    if 满足结束条件:
        将路径加入结果集
        return
    
    for 选择 in 选择列表:
        # 1. 做出选择
        将该选择从选择列表中移除
        路径.append(选择)
        
        # 2. 进入下一层决策树
        backtrack(新的路径, 新的选择列表)
        
        # 3. 撤销选择 (回溯)
        路径.pop()
        将该选择重新加入选择列表

代码示例

示例 1：全排列 (Permutations)

问题：给定一个没有重复数字的列表，返回其所有可能的全排列。例如，[1, 2, 3] 的全排列为：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。

思路：

路径：当前已经选择的数字列表。
选择列表：所有还没有被选择的数字。
结束条件：当路径的长度等于原始列表长度时，说明找到了一个完整排列。

def permute(nums):
    """
    使用回溯法生成全排列
    :param nums: List[int]
    :return: List[List[int]]
    """
    res = []  # 存储最终结果

    def backtrack(path, choices):
        # 结束条件：路径长度等于原列表长度，找到一个排列
        if len(path) == len(nums):
            res.append(path[:])  # 注意：这里必须用切片path[:]复制一份，否则后续修改会影响已存入的结果
            return

        for i in range(len(choices)):
            # 做出选择：选择choices[i]
            path.append(choices[i])
            # 剩余的选择列表为：choices中除去当前选择的部分
            remaining = choices[:i] + choices[i+1:]
            # 递归进入下一层
            backtrack(path, remaining)
            # 撤销选择（回溯）
            path.pop()

    backtrack([], nums)
    return res

# 测试
print(permute([1, 2, 3]))
# 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

示例 2：子集 (Subsets)

问题：给定一组不含重复元素的整数数组，返回该数组所有可能的子集（幂集）。例如，[1, 2] 的子集为：[[], [1], [2], [1,2]]。

思路：

路径：当前已经选择的元素。
选择列表：每次从起点start之后的元素中选择（避免重复）。
结束条件：没有明确的终止条件，每个节点（包括根节点）都代表一个子集，所以一开始就记录路径。

def subsets(nums):
    """
    使用回溯法生成子集
    :param nums: List[int]
    :return: List[List[int]]
    """
    res = []

    def backtrack(start, path):
        # 每个节点都记录当前路径（子集）
        res.append(path[:])

        # 从start开始遍历，避免产生重复子集
        for i in range(start, len(nums)):
            # 做出选择
            path.append(nums[i])
            # 进入下一层，注意下一个起点是i+1，不是start+1
            backtrack(i + 1, path)
            # 撤销选择（回溯）
            path.pop()

    backtrack(0, [])
    return res

# 测试
print(subsets([1, 2, 3]))
# 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

实践练习

练习 1：字母大小写排列 (简单)

问题：给定一个字符串s，其中可以包含字母和数字。将字符串中的每个字母转变大小写，可以得到一个新的字符串。返回所有可能得到的新字符串。例如，输入 "a1b2"，输出 ["a1b2", "a1B2", "A1b2", "A1B2"]。

要求：

使用回溯法实现。
遇到数字则直接加入路径，遇到字母则尝试大写和小写两种选择。

练习 2：生成所有子集 (中等)

问题：给定一个可能包含重复元素的整数列表nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。例如，输入 [1, 2, 2]，输出 [[], [1], [1,2], [1,2,2], [2], [2,2]]。

要求：

先对数组排序，以便于处理重复元素。
在回溯的for循环中，判断当前元素是否和前一个元素相同且前一个元素未被使用过（在同一层递归中），如果是则跳过，以避免生成重复子集。

练习 3：组合总和 (中等)

问题：给定一个无重复元素的整数数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。例如，输入 candidates = [2,3,6,7], target = 7，输出 [[7], [2,2,3]]。

要求：

使用回溯法。
注意：同一个数字可以被重复选择，所以在递归时下一个选择的起点可以是当前位置i，而不是i+1。

常见错误

引用与拷贝问题：在递归结束时将路径存入结果集，务必使用path[:]或list(path)进行深拷贝。直接使用res.append(path)会导致所有结果指向同一个列表对象，最终结果会全部为空或最后一个状态。
忘记回溯：在做出选择并递归返回后，必须撤销该选择（path.pop()），否则会影响同一层其他分支的选择。
对选择范围理解错误：在全排列问题中，选择列表是“所有未使用的数字”；在子集/组合问题中，为了防止重复，选择列表通常是“当前起点之后的所有数字”。混淆两者会导致结果重复或遗漏。
结束条件设置不当：没有正确设置递归的终止条件，导致无限递归或结果不完整。

小结

回溯法是一种非常强大的算法范式，用于解决组合、排列、子集等“搜索所有可能性”的问题。其核心可以概括为：

核心思想：试错法。在递归过程中做选择，如果发现当前选择不满足约束条件，就撤销选择并返回上一步尝试其他选择。
关键步骤：
1. 做出选择：从当前可选列表中选择一个元素。
2. 递归调用：带着新的路径和选择列表，进入下一层决策。
3. 撤销选择（回溯）：将状态恢复到做选择之前，以便尝试其他选项。
状态表示：通常需要维护一个path（当前路径）和在递归参数中控制选择范围的start或used数组。

记住回溯法的通用框架，是解决一大类搜索问题的关键。下一课我们将用这个框架来解决经典的 N 皇后问题。

练习编辑器

rust