摘要
- 回溯和递归是相辅相成的，用到回溯的地方一般都会有递归。递归是实现回溯的基本方法。
- 回溯法并不是很高效的算法，是一种暴力枚举法，通过枚举可能答案来解决问题。
- 回溯法提供了一种枚举各种可能性的方法，让一些难以用多层循环搜索答案的问题至少能用回溯法解决，如组合问题和切割问题。
- 所有的回溯法的问题都可以抽象为树形结构，即可能答案的构造是树形的。
回溯法基础
相关定义和概念
- 定义：回溯法也可以叫做回溯搜索法，是一种搜索的方式。
- 组合：可以理解为数学上的集合，并不强调元素的顺序和相对位置。
- 排列：可以理解为数学上的数列，强调元素的顺序。
回溯法的意义
- 回溯法的本质是穷举，穷举所有可能的答案，然后验证这些答案是否符合题目要求，选出合适的答案。
- 有一些问题只能用回溯法解决，目前并没有更高效的解法。
回溯法的理解
- 可能答案的枚举过程是树形的，可以通过画出答案的构造树来帮助思考。
- 回溯法的过程都可以抽象为N叉树。
- 回溯法解决的问题是在给定集合中递归查找子集，集合的大小决定了答案树的宽度（一个节点有几个孩子），递归的深度构成了答案树的深度。
- 递归用于向下找，循环用于在同一层中找
递归与循环
回溯法的模板
- 回溯法的递归函数一般没有返回值。
- 递归函数一般命名为
backtracking。 - 回溯法的参数列表在一开始是不好确定的，会在分析问题的过程中逐渐完善。
- 先写递归的终止条件，在终止条件下收集结果。
- 然后写单层搜索的逻辑，一般情况下是
for循环，用来处理当前集合里的每一个元素。用答案树来看，也可以对应处理当前节点的每一个子节点。 -
for循环中一般做三件事：1. 处理当前节点；2. 调用递归函数；3. 撤销操作（回溯）
void backtracking(arg...) {
if (/* 终止条件 */) {
/* 收集结果 */
return;
}
for (/* 每一个集合中的元素 */) {
/* 1. 处理当前元素 */
/* 2. 调用递归函数 */
/* 3. 撤销处理（回溯） */
}
return;
}
还要继续理解和总结，先多写一些回溯法的题目。
LeetCode77 组合
- 初见题目的想法：按照以上的回溯模板进行思考
- 首先回溯法的递归函数不返回值
- 递归函数命名为
backtracking - 在分析问题的过程中确定参数列表
- 先写递归的终止条件：当前组合
cur的元素个数cur.size()等于k，则收集当前组合cur，然后直接返回。（这步确定需要传入的参数为结果集res，当前组合cur，元素个数k） - 再写单层搜索的逻辑：用
for循环向cur中尝试加入元素（这步确定需要传入的参数为n，还有防止组合重复所需的元素的起始值j。
- 按照回溯法的模板进行思考，可以很容易的写出如下代码。我将当前组合命名为
cur，和遍历二叉树时对节点的命名类似，提醒自己用树的形式去理解回溯法。cur对应的就是答案的构造树上的某个节点。
初见题目的题解代码如下
class Solution {
public:
void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = j; i <= n; i++) {
cur.push_back(i);
backtracking(res, n, k, cur, i + 1);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
backtracking(res, n, k, cur, 1);
return res;
}
};
以上代码的递归函数的参数列表里的cur没有传引用（vector<int> cur），多次拷贝vector，代码效率较差。
改为传引用vector<int>& cur，可见能显著提升效率。
class Solution {
public:
void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = j; i <= n; i++) {
cur.push_back(i);
backtracking(res, n, k, cur, i + 1);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
backtracking(res, n, k, cur, 1);
return res;
}
};
-
组合问题较简单，在这里在复习一次回溯法的三步思考来总结今天的复习：
- 在分析问题的过程中确定递归函数需要的参数
- 确定递归的终止条件，在终止条件里收集结果
- 确定单层递归的处理逻辑
剪枝待第二天复习。
