代码随想录算法训练营第60期第二十二天打卡

        大家好！我们今天来到了一个全新的章节，回溯算法，那究竟什么是回溯算法，我们应该如何理解回溯算法，以及回溯算法可以解决的题目，我们今天就来一探究竟。

第一部分 回溯算法理论基础

        其实我可以告诉大家的是回溯算法其实本质上就是暴力，其实并不是什么高效的算法，但是有一些类型的题目不用回溯算法就解决不了，其实我们后面的图论里面会有一道题叫做所有可达的路径，那里其实就是递归与回溯相辅相成，那里的dfs(深度优先搜索)本质上就是递归，其实回溯本质就是暴力枚举（穷举），我们的确可以通过一些剪枝的操作来尽可能减小时间复杂度，但其实我们还是改变不了回溯的本质是暴力，有一些问题能暴力搜素出来就不错了，所以我们不得不采用回溯的算法。

        那么回溯算法可以解决什么样的题目呢？首先我们可以解决以下几类问题：

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

       这些我们在后面都会有所涉及，大家只需要了解一下就可以了，还有回溯的模板，回溯其实是在一棵树上进行操作的，回溯法解决的都是在集合中递归查找子集，递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

       那么提到递归的模板其实大家刷题刷多了逐渐有了自己的理解以后自然就会总结出属于自己的模板，我在这里简单提一下：

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

      先找到递归的终止条件，加下来是遍历搜索符合条件的节点，然后回溯，因为我们还会有下一次操作，递归与回溯两者不可分割，就比如说我要找3的全排列的所有情况，1后面可以有2，3，如果我找全了一种情况，我就必须回溯才能找全所有情况，这个大家要注意。好了那我们就开始尝试一下今天的回溯算法的题目了。

第一题对应力扣编号为77的题目组合

       我们来到今天的第一题，这个应该可以算是回溯算法的入门题目了，我们来看一下题目要求：

        题目的意思是给出两个数求出给定范围内的给定个数的组合数，这个如果不用回溯算法的话真的似乎没有其他的方法了，其实我给大家举一个例子，比如说1，2，3，4我要找出所有大小为2的组合，其实大家可以很轻松的写出代码，就是两层嵌套的for循环即可：

#include <iostream>
#include <vector>using namespace std;
vector<int> vec = {1, 2, 3, 4};
int main()
{for (int i = 0; i < vec.size(); ++i){for (int j = i + 1; j < vec.size(); ++j){cout << vec[i] << " " << vec[j] << '\n'; }}return 0;
}

     如果是找出所有大小为3的组合呢？大家也可以快速写出代码：

#include <iostream>
#include <vector>using namespace std;
vector<int> vec = {1, 2, 3, 4};
int main()
{for (int i = 0; i < vec.size(); ++i){for (int j = i + 1; j < vec.size(); ++j){for (int k = j + 1; k < vec.size(); ++k){cout << vec[i] << " " << vec[j] << " " << vec[k] << '\n';}}}return 0;
}

      其实我们可以看出，一旦组合的长度大了，我们的for嵌套很多就会导致超时，因为我们需要想一种方法，我们要先清楚一个问题其实我们的回溯算法本质是通过一棵树来实现的：

       但是大家还要时刻注意我们都要取不同的元素，比如说为什么取了2后面不会出现【2，1】这种情况就是考虑到了组合是无序的，【1，2】与【2，1】算作同一个，而且每一个元素只能去一次，自然也不会出现【2，2】的情况，大家了解了树形结构以后，接下来就是很重要的写代码环节，结合我们二叉树章节的递归三部曲，我们就可以尝试写出本题的代码：

class Solution {
private:vector<int> path;vector<vector<int>> result;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();}}
public:vector<vector<int>> combine(int n, int k) {path.clear();result.clear();backtracking(n, k, 1);return result;}
};

       我们来理解一下，其实如果初次接触回溯算法的话还是很难的，首先我们借助一个数组存储我们当前正在搜索到路径，当长度够了的时候我们就到了单次递归的终止条件，我们就把我们搜索到的路径添加到二维数组里这样我们就返回二维数组，这是我们题目要求我们返回的结果，大家尤其注意我中间的递归逻辑，我们一定不要忘记回溯，如果我们搜索到了【1，2】这条路只有回溯我们才可以搜索到【1，3】这条路，这就是回溯的意义，不要忘记任何的可行解，而且时刻注意我们参数的变化，注意我们起始的索引，保证不重复就可以了。

第二题对应力扣编号为216的题目组合总和III

       我们来到了今天的第二道题目，其实前面的那道题我们是可以做剪枝操作的，但是我们先不看我们先理解好回溯算法再去考虑如何优化，我们来看一下这道题目是什么意思：

       题目意思很好明白，其实比上一题给我们添加了一个限制条件而已，就是要求我找到的组合的和必须是给定值，我们应该如何考虑呢？其实我们还是得注意递归的终止条件以及回溯过程，如果说我们找到了一个符合要求的组合我们就添加进二维数组里面最后返回二维数组即可：

class Solution {
private:vector<int> path;vector<vector<int>> result;//解释一下我们递归函数的参数与返回值这不也是我们递归三部曲的第一步第一个参数targetSum是题目给的目标和//k表示要求的长度，sum存储的是当前的和，startIndex是起始的索引就是可以搜索的元素void backtracking(int targetSum, int k, int sum, int startIndex){//这里递归的终止条件与上面的题目有所不同其实要求会更多if (path.size() == k){//不仅仅长度要求需要满足而且和也需要满足才可以if (sum == targetSum){result.push_back(path);return;}}//单层递归的逻辑for (int i = startIndex; i <= 9; ++i){//首先将该元素添加到sum种然后添加到数组中sum += i;path.push_back(i);backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex//然后回溯就是减去i然后再将当前元素退出数组sum -= i;path.pop_back();}}
public:vector<vector<int>> combinationSum3(int k, int n) {result.clear();path.clear();backtracking(n, k, 0, 1);return result;}
};

      具体的过程我在代码注释里面解释的很清楚，大家多多思考，理解回溯不容易。

第三题对应力扣题号为17的题目电话号码的字母组合

      这是今天的最后一道题目，我们直接来看一下题目要求是什么：

       其实这里存在一个映射，就是一个数字对应几个字母，给出我们两个数字字符求出所有存在的字母的组合，我们应该如何思考？

class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string &digits, int index){//递归的终止条件if (index == digits.size()){result.push_back(s);return;}//转换为整型数字(方便去寻找对应的字母)int digit = digits[index] - '0';string letters = letterMap[digit];      // 取数字对应的字符集//这样我们开始找对应的字母for (int i = 0; i < letters.size(); ++i){s.push_back(letters[i]);backtracking(digits, index + 1);s.pop_back();}}vector<string> letterCombinations(string digits) {s.clear();result.clear();//如果给出的数字字符串是0就直接返回空数组就可以if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};

      这个题目有点抽象容易搞混，我们的映射就实现了数字与字母的关系，我们还需要去遍历当前要求的数字所对应的字母字符串在这期间我们才可以使用递归与回溯，一个个字母去找，找完第一个数字对应的再去找下一个直到达到了题目给出数字字符串的长度即可。

今日总结

      回溯算法其实是很重要的，我们在后面的图论会反复使用，大家理解好递归三部曲就好，搞明白我们回溯的对象是谁，具体题目具体分析就可以了。今天我们就到这里，我们下一次再见！