代码随想录训练营第24天|回溯算法理论基础、LeetCode 77.组合

参考

代码随想录

回溯算法理论基础

什么是回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，所以效率很低，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。在某些情况下不得不使用回溯算法。

回溯算法解决的问题

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

如何理解回溯算法

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成的树的深度。

回溯模板

回溯三步曲：

• 回溯函数返回值和参数
  回溯算法中函数返回值一般为void，回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数);
1

• 回溯函数终止条件
  当找到满足条件的一个答案，把这个答案存放起来，并结束本层递归

if (终止条件) {
    存放结果;
    return;
}
1
2
3
4

• 回溯搜索的遍历过程
  回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
  

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次，backtracking这里自己调用自己，实现递归。

图中for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

完整的递归模板如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11

LeetCode 77.组合

• 递归函数的参数和返回值
  不需要返回值，需要传入数据区间范围n，每个组合的大小k，以及每次递归的起始位置startIndex

void backtracking(int n,int k,int startIndex);
1

另外还需要两个全局变量来存储遍历路径和最终的结果，当然也可以作为参数，但是参数太多，多次递归会影响效率。

vector<int> path;
vector<vector<int>> result;
1
2

• 递归终止条件
  path中保存着遍历的结果，当path.size() == k的时候说明已经找到了一种满足条件的答案，此时需要保存这个答案，并结束本轮递归。

if(path.size() == k){
	result.push_back(path);
	return;
}
1
2
3
4

• 单层搜索过程
  用for循环来遍历树的宽度，递归遍历树的深度，如下图所示：
  

for(int i = startIndex; i <= n; i++){
	path.push_back(i);
	backtracking(n,k,i+1);
	path.pop_back();
}
1
2
3
4
5

注意，for循环中的递归调用的startIndex参数要赋值为i+1。
完整的代码实现如下：

class Solution {
public:
    void backtracking(int n,int k,int startIndex)
    {
        if(path.size() == k){
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i <= n; i++){
	        path.push_back(i);
	        backtracking(n,k,i+1);
	        path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
private:
    vector<int> path;
    vector<vector<int>> result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

剪枝优化

所谓的剪枝优化就是去除一些不必要的遍历来提高效率。
就这题而言，如果剩余的元素个数已经不足所需要的元素个数的时候就没有必要继续遍历，可以直接终止。
对于一般情况，已经选择的元素个数：path.size()， 还需要的元素个数为: k - path.size()，因此如果剩余的元素个数小于k-path,size()，那么这种情况肯定不能满足，因此可以直接终止。因此可以得到下面的关系式：

(i - 1) + k - path.size() <= n 
1

其中1 <= i <= n，k-path.size()是还需要的元素个数，因为i表示的是当前元素，并且这个元素还未使用，所以i-1表示的就是上一个已经用过的元素，因此上式表示的意思就是已经使用过的元素个数加上还剩余的元素个数要小于等于总的元素个数n。举个例子，比如，当前path中没有，k = 2，那么还需要2个元素，因此i只能小于等于3，满足上面的关系式，对上面的关系式稍做处理，得到：

i <= n - k + paht.size() + 1
1

因此优化针对的就是for循环的结束条件，原来的for循环改为

for(int i = startIndex; i <= n - k + path.size() + 1; i++)
1

这样修改之后相比于原来效率有一定的提升，但总的来说效率还是比较低的。