TNotes.algorithms

Appearance

0034. 回溯

0034. 回溯 ​

1. 🎯 本节内容 ​

  • 回溯算法简介
  • 核心概念：尝试、回退、剪枝
  • 回溯相关 LeetCode 例题

2. 🫧 评价 ​

回溯算法的核心思：选择、探索与撤销，可以概括为一个“前进 -> 失败 -> 后退 -> 再前进”的循环过程。这个过程由三个关键要素驱动：

要素描述
选择 Choice在每一步，我们都有一个可选的“选择列表”，我们需要从中做出一个选择，从而向解前进一步。
约束 Constraint判断当前路径是否满足问题的约束条件，如果不满足，就进行“剪枝”，不再继续探索这条路径。
目标 Goal当路径满足结束条件时，说明我们已经找到了一个有效的解，可以将其记录下来。

其中，选择和约束没有固定的先后顺序，你可以先根据“约束条件”来计算“选择列表”，也可以直接从“选择列表”中做出一个具体的选择之后再进行“约束检查”。这一步就是所谓的“剪枝”，提前剪掉那些不满足条件的搜索路径，是回溯算法的核心优化点。

TIP

在刷回溯算法题的时候，若不熟悉，可以拿出纸笔画一画回溯的路线图，这能很好地帮我们理解回溯的套路。

3. 🤔 回溯算法是什么？ ​

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

它是一种通过“试错”来寻找问题所有可能解的算法策略。你可以把它想象成在一个迷宫里找路：沿着一条路走下去，如果发现是死胡同，就退回到上一个岔路口，换一条路继续尝试，直到找到所有出口。

它本质上是对解空间树进行深度优先搜索（DFS），但在搜索过程中，一旦发现当前路径不可能得到有效解，就会立即“剪枝”，即放弃对该路径的继续探索，并撤销上一步的选择，回到之前的状态，尝试其他可能性。

常见的回溯算法术语：

术语描述
解（solution）解是满足问题特定条件的答案，可能有一个或多个
约束条件（constraint）约束条件是问题中限制解的可行性的条件，通常用于剪枝
状态（state）状态表示问题在某一时刻的情况，包括已经做出的选择
尝试（attempt）尝试是根据可用选择来探索解空间的过程，包括做出选择，更新状态，检查是否为解
回退（backtracking）回退指遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态
剪枝（pruning）剪枝是根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率

TIP

问题、解、状态等概念是通用的，在分治、回溯、动态规划、贪心等算法中都有涉及。

4. 🤔 什么是「尝试与回退」？ ​

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

  • 尝试 ≈ 前进 ≈ push
  • 回退 ≈ 撤销 ≈ pop

svg

5. 🤔 什么是「剪枝」？ ​

回溯算法效率的关键在于“剪枝”（Pruning）。复杂的回溯问题通常包含一个或多个约束条件，剪枝就是在搜索过程中，通过约束条件提前判断并排除那些不可能产生有效解的路径，从而避免无效的尝试，以达到优化算法的目的。

可以将“剪枝”理解为：“剪去不必要的搜索”，主要表现为：

  • 在搜索开始之前：排除那些不可能生成有效解的路径
  • 在搜索过程中：在链路上一旦发现不满足条件的路径，就立即停止搜索，返回上一级状态

6. 🤔 回溯算法的「通用框架代码」是什么样的？ ​

python
def backtrack(state: State, choices: list[choice], res: list[state]):
    """回溯算法框架"""
    # 1. 记录：判断是否为解
    if is_solution(state):
        # 1.1 记录解
        record_solution(state, res)
        # 1.2 不再继续搜索
        return
    # 2. 遍历：所有选择
    for choice in choices:
        # 3. 剪枝：提前结束无效路径的搜索
        if is_invalid(state, choice):
            continue
        # 4. 尝试：做出选择，更新状态
        make_choice(state, choice)
        # 5. 递归：进入下一级状态
        backtrack(state, choices, res)
        # 6. 回退：撤销选择，恢复到之前的状态
        undo_choice(state, choice)

7. 🤔 回溯算法的「优点与局限性」是什么？ ​

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。

然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。

  • 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
  • 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。

  • 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
  • 启发式搜索：在搜索过程中引入一些策略（比如对搜索源数据先进行排序）或者估计值，从而达到以下目的：
    • 优先搜索最有可能产生有效解的路径
    • 优化失败路径上的尝试次数，提前判定当前尝试的路径是无效解

8. 🤔 回溯算法的「典型例题」有哪些？ ​

回溯题更适合按“搜索形态”来理解，实际刷题时，常见题型大致如下：

题型核心特征典型例题
组合 / 子集从候选集合中不断做“选或不选”的决策，重点是控制起点、防止重复选择。77. 组合、39. 组合总和、40. 组合总和 II、78. 子集、90. 子集 II
排列顺序不同就算不同答案，通常需要使用 used 数组或交换法来标记已选元素。46. 全排列、47. 全排列 II
棋盘 / 约束满足每走一步都要检查约束是否合法，剪枝效果往往决定性能上限。51. N 皇后、37. 解数独
字符串切分 / 映射在字符串上枚举切分位置或字符映射，适合练习“路径 + 终止条件 + 回退”。17. 电话号码的字母组合、131. 分割回文串、93. 复原 IP 地址
网格搜索在二维平面中沿着路径不断尝试与回退，通常要配合访问标记。79. 单词搜索、980. 不同路径 III
集合划分 / 装桶通过“把当前元素放入哪个桶”来搜索，通常需要排序、剪枝和去重。698. 划分为 k 个相等的子集、473. 火柴拼正方形

这些题的共同点是：都需要维护“当前路径”，枚举“下一步选择”，在不满足约束时尽早剪枝，并在递归返回时撤销现场。

TIP

若题目更偏向“求最优值”而不是“找出所有可行解”，则还需要和动态规划、贪心、状态压缩等方法一起比较，回溯不一定是最优解法。

9. 🔗 引用 ​

Discussions