代码随想录算法训练营第二十二天|Day22 回溯算法
回溯算法理论基础
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
相信大家看着这些之后会发现，每个问题，都不简单！
另外什么是组合，什么是排列？
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。记住组合无序，排列有序，就可以了。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯法模板
这里给出Carl总结的回溯算法模板。
在讲二叉树的递归 (opens new window)中我们说了递归三部曲，这里再出回溯三部曲。
- 回溯函数模板返回值以及参数
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
- 回溯函数终止条件
既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
- 回溯搜索的遍历过程
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
分析完过程，回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
77. 组合
题目链接/文章讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作：https://www.bilibili.com/video/BV1wi4y157er
思路
int* path;
int pathTop;
int** ans;
int ansTop;
void backtracking(int n, int k,int startIndex) {
if(pathTop == k) {
int* temp = (int*)malloc(sizeof(int) * k);
int i;
for(i = 0; i < k; i++) {
temp[i] = path[i];
}
ans[ansTop++] = temp;
return ;
}
int j;
for(j = startIndex; j <= n- (k - pathTop) + 1;j++) {
path[pathTop++] = j;
backtracking(n, k, j + 1);
pathTop--;
}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
path = (int*)malloc(sizeof(int) * k);
ans = (int**)malloc(sizeof(int*) * 10000);
pathTop = ansTop = 0;
backtracking(n, k, 1);
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) *(*returnSize));
int i;
for(i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = k;
}
return ans;
}学习反思
通过回溯算法，将符合条件的组合存储在一个二维数组中返回。在回溯的过程中，首先判断当前path数组中元素的个数是否达到k个，若达到则将其存储在ans二维数组中，然后返回继续回溯。若未达到k个，则从startIndex开始遍历数字，将当前数字放入path数组中，然后进行递归回溯，最后进行回溯弹出当前数字。在函数combine中，首先动态申请path和ans数组的空间，然后调用backtracking函数进行回溯算法的求解，最后设置返回大小和returnColumnSizes数组的值，最后返回ans数组。时间复杂度为O(C(n, k) * k)。
216.组合总和III
题目链接/文章讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
视频讲解：https://www.bilibili.com/video/BV1wg411873x
思路
int* path;
int pathTop;
int** ans;
int ansTop;
int getPathSum() {
int i;
int sum = 0;
for(i = 0; i < pathTop; i++) {
sum += path[i];
}
return sum;
}
void backtracking(int targetSum, int k, int sum, int startIndex) {
if(pathTop == k) {
if(sum == targetSum) {
int* tempPath = (int*)malloc(sizeof(int) * k);
int j;
for(j = 0; j < k; j++)
tempPath[j] = path[j];
ans[ansTop++] = tempPath;
}
return;
}
int i;
for (i = startIndex; i <= 9; i++) {
sum += i;
path[pathTop++] = i;
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i;
pathTop--;;
}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes){
path = (int*)malloc(sizeof(int) * k);
ans = (int**)malloc(sizeof(int*) * 20);
pathTop = ansTop = 0;
backtracking(n, k, 0, 1);
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = k;
}
return ans;
}学习反思
通过回溯算法，将符合条件的组合存储在一个二维数组中返回。在回溯的过程中，首先判断当前path数组中元素的个数是否达到k个，若达到则判断当前组合的和是否等于目标值targetSum，若相等则将其存储在ans二维数组中，然后返回继续回溯。若未达到k个，则从startIndex开始遍历数字，将当前数字放入path数组中，然后进行递归回溯，最后进行回溯弹出当前数字。在函数combinationSum3中，首先动态申请path和ans数组的空间，然后调用backtracking函数进行回溯算法的求解，最后设置返回大小和returnColumnSizes数组的值，最后返回ans数组。时间复杂度为O(C(n, k) * k)。
17.电话号码的字母组合
题目链接/文章讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html
视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug
思路
char* path;
int pathTop;
char** result;
int resultTop;
char* letterMap[10] = {"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
void backTracking(char* digits, int index) {
if(index == strlen(digits)) {
char* tempString = (char*)malloc(sizeof(char) * strlen(digits) + 1);
int j;
for(j = 0; j < strlen(digits); j++) {
tempString[j] = path[j];
}
tempString[strlen(digits)] = 0;
result[resultTop++] = tempString;
return ;
}
int digit = digits[index] - '0';
char* letters = letterMap[digit];
int i;
for(i = 0; i < strlen(letters); i++) {
path[pathTop++] = letters[i];
backTracking(digits, index+1);
pathTop--;
}
}
char ** letterCombinations(char * digits, int* returnSize){
path = (char*)malloc(sizeof(char) * strlen(digits));
result = (char**)malloc(sizeof(char*) * 300);
*returnSize = 0;
if(strlen(digits) == 0)
return result;
pathTop = resultTop = 0;
backTracking(digits, 0);
*returnSize = resultTop;
return result;
}学习反思
在backTracking函数中，首先判断当前index是否等于digits数组的长度，若等于，则表示已经处理完所有的数字，将当前的path数组复制到一个新的字符串数组中，并将其存储在result中。然后进行递归，处理下一层数字（index+1）。在递归的过程中，先将字符数字转换为真正的数字，并找到对应的字符串，然后将字符串中的每个字符依次放入path数组，再进行递归回溯。最后回溯弹出字符，恢复到上一层状态。在函数letterCombinations中，首先动态申请path和result数组的空间，然后判断digits数组是否为空，若为空则直接返回空集，若不为空，则调用backTracking函数进行回溯算法的求解。最后设置返回大小为resultTop，并返回result数组。时间复杂度为O(3^N * 4^M)。
总结
对递归有了更深的理解，加油！！！