概念


百度百科： 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 [1]

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。 用回溯算法解决问题的一般步骤： 1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。 2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。 3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

回溯法的效率

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

回溯法解决的问题

虽然回溯法效率不高，但一些问题只能用回溯（暴力搜索）

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

注：组合不强调元素间的顺序，排列强调元素间的顺序
具体题录见刷题笔记回溯部分

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

回溯法模板

还是按照递归三部曲来理解：

  1. 回溯函数模板返回值及参数

回溯算法的返回值一般是void，参数需要根据逻辑来确定
void backtracking(参数)

  1. 回溯终止条件

对于树来说，可能遍历到叶子节点了就要退出
对于回溯来说，找到了满足条件的一条答案，就要把答案存起来，然后结束本层递归

if (终止条件) {
    存放结果;
    return;
}
  1. 单层递归的逻辑（回溯搜索的遍历过程）

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
image.png
回溯函数遍历过程的伪代码：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}