1. 什么是回溯法

所谓回溯，说的简单点，假如有一个分岔口，有 n 条路可以走，但是只有一条路是正确的，问题是你不知道哪条是正确的路，所以只能一个一个的试，当你选了一条路走后，发现这条路走不通，你就需要原路返回，重新回到分岔口，然后再选另一条路走下去，这就是回溯。

回溯法并不是什么高效的算法，因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

事实上，回溯是递归的副产品，只要有递归就会有回溯。回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，就是树的深度。

⭐ 回溯法的基本思想：

• 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树

• 算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解

  • 如果肯定不包含，则跳过对该结点为根的子树的搜索（剪枝 pruning），逐层向其祖先结点回溯

    💡 搜索时，常用两种策略避免无效搜索（剪枝函数）

    • 用约束条件剪去得不到可行解的子树
    • 用目标函数剪去得不到最优解的子树

  • 否则，进入该子树，继续按深度优先策略搜索

⭐ 回溯法时间复杂度的计算：

• 每一个节点能够做的选择有几种树高回溯中调用的其他方法的时间复杂度

2. 解空间树

问题的解空间一般用解空间树的方式组织：

• 树的根节点位于第一层，表示搜索的初始状态
• 第二层的节点表示对解向量的第一个分量做出选择后到达的状态
• 第一层到第二层的边上标出对第一个分量选择的结果
• 依此类推，从树的根节点到叶子节点的路径就构成了解空间的一个可能解

回溯法求解时常见的两类解空间树：

• 子集树
• 排列数

排列树

当所给问题是找出给定的 n 个元素满足某种性质的所有排列时，相应的解空间树称为排列树（强调元素顺序）

下面给出解题模板：

解决一个回溯问题，实际上就是一个解空间树的遍历过程。你只需要思考 3 个问题：

• 路径：也就是已经做出的选择(已经选择的节点)
• 选择列表：也就是当前节点可以做的选择（对于当前节点来说，它可以往哪边走？）
• 结束条件：也就是到达决策树底层，无法再做选择的条件

result = []
def backtrack(选择列表, 路径):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表: (横向遍历)
        排除不合法的选择（剪枝）
        做选择
        进入下一层解空间树 backtrack(选择列表, 路径) (纵向遍历，递归) 
        撤销选择（回溯）

⭐ 感觉不是很难理解吧，其实就是一层层地遍历解空间树中的节点，每个节点你可以视为一个分岔口，这个节点的 n 个孩子节点就是分岔口的 n 条路，通过回溯遍历这 n 条路，找到正确的选择。

子集树

当所给问题是从 n 个元素的集合 S 中找出满足某种性质的子集时，相应的解空间树称为子集树（不强调元素顺序）

对于子集树问题，另需要一个标志位 i（也可能需要多个），表示解空间的第 i 个位置（或者表示在解空间中的数量等），往往从 0 开始，当 i = 解空间的大小 时，表示解空间上的所有位置的解都已经求出

💡 可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠标志位。

result = []
def backtrack(选择列表, 路径, 标志位):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        排除不合法的选择（剪枝）
        做选择
        进入下一层解空间树 backtrack(选择列表, 路径, 标志位 + 1 等 随机应变)
        撤销选择（回溯）

还有种特殊情况，就是题目根本就没啥结束条件，只要有子集，就立马加入到 res 中，典型例题如 剑指 Offer II 079. 所有子集 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)，这种题目的解法模板如下：

result = []
def backtrack(选择列表, 路径, 标志位):
    result.add(路径)

    for 选择 in 选择列表:
        排除不合法的选择（剪枝）
        做选择
        进入下一层解空间树 backtrack(选择列表, 路径, 标志位 + 1 等 随机应变)
        撤销选择（回溯）

当然了，不可能所有的问题都可以用这两种解空间树，但是回溯的思想其实是一致的，无外乎三步：选择、进入下一层的递归、撤销选择