回溯
- 本质上:穷举 + 剪枝。
- 回溯法就是解决这种k层for循环嵌套的问题。
- for循环横向遍历,递归纵向遍历,回溯不断调整结果集。
- 注意画出 解空间树-N叉树。
细节
模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
题型
组合
N个数里面按一定规则找出k个数的集合。
- 细节
- 需要保存N叉树所有符合的结果——叶子,定义path、ans,而将path加入ans的方法细节。
- 在C++中,当使用 push_back() 函数将一个元素添加到 std::vector 容器中时,如果该元素是一个对象,那么它可以通过值传递或者引用传递的方式进行添加。如果传递的是一个对象的引用,那么新元素就会引用这个对象。一般是直接传递对象,进行值传递,拷贝一个path。
- 剪枝
- 对N叉树的高度剪枝,在每次进入下一层递归前进行判断剪枝(或者在递归函数开始之前,相当于在模板的终止条件之前),记得回溯。
- 对N叉树的宽度剪枝,for循环的范围剪枝,剩余个数是否满足条件。
- 类型
- 单个集合、多个集合
- 单个集合内的组合,用到
beginIdx
,当前元素从该集合哪开始。
- 多个集合间的组合,用到
index
,当前元素从哪个集合得到。
- 组合没有数量要求
- 没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回。
- 元素可无限重复选取
- 关键点:进入下一层递归不用i+1,表示可以重复读取当前的数。
- 去重——参照解空间树
- 树枝去重
- 同一种组合内不可以有重复元素,即一种树枝路径为一种组合结果。
- 树层去重
- 不同组合 不允许相同
- 一般 都会利用 used数组 和 排序 辅助 树层去重。
- used数组
在candidates[i] == candidates[i - 1]相同的情况下:
- used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false,说明同一树层candidates[i - 1]使用过
- 该used数组 也需要 记得 回溯。
分割
一个字符串按一定规则有几种切割方式。
-
细节
-
类似组合问题,抽象为N叉树。
-
切割线:用beginIdx
模拟。
-
终止条件
- 一种,当前方案已经切割到了最后,即
beginIdx == end
,可以直接加入path——解空间树一条路径。
- 一种,在倒数第二位置时,最后一段已经确定了,只需要判断最后一段(叶子)是否合法,再决定是否加入该条路径path。
-
拼接vector<string>
#include<numeric>
ans.push_back(
accumulate(path.begin(), path.end(), string{},
[](const string& a, const string& b)->string {return a.empty() ? b : a + "." + b; })
);
子集
一个N个数的集合里有多少符合条件的子集。
- 细节
- 遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合,可能根据条件对节点进行筛选。
- 求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树。
- 终止条件问题
- 可以忽略终止条件,这是因为
for
从 beginIdx
开始且下一层是i+1
,for
会到达size
。
- 类型
排列
N个数按一定规则全排列,有几种排列方式。
- 细节
- 排列问题,每次都要从头开始搜索。
- 每层都是从0开始搜索,不使用
beginIdx
。
- 使用used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次。
- 去重
棋盘问题
N皇后,解数独等等。
N皇后问题
- 细节
- 解空间树,最大高度即棋盘边长,宽度也是。
- 每一递归表示一层,对于棋盘中的一行,又由于回溯操作,所以在检查该棋子是否能放置时同行不需要检查。
- 终止条件:当前行==n,棋盘边长。
解数独问题
- 细节
- 不同于N皇后问题,数独问题,每一行的每一个空格都要填充数字,所以起始行永远=0。
- 终止条件:没有终止条件,全部填充即可,充分利用回溯函数的返回值bool。
其他
总结