代码随想录算法训练营day22

代码随想录算法训练营

—day22

---

前言

今天是算法营的第22天，希望自己能够坚持下来！
今日任务：
● 回溯算法理论基础
● 77. 组合
● 216.组合总和III
● 17.电话号码的字母组合

---

回溯算法理论基础

文章讲解

• 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
• 回溯是递归的副产品，只要有递归就会有回溯。
• 回溯的本质是穷举，是一种纯暴力的方法，嵌套多个for循环 回溯法解决的问题都可以抽象为树形结构
• 回溯的递归函数一般叫backtracking，返回值一般为void，参数比较多，没那么容易确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯法解决的问题

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

回溯法模板

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

---

一、77. 组合

题目链接
文章讲解
视频讲解

思路：

1. 递归函数的参数和返回值：参数：n，k，startIndex（每一层递归需要避开已经遍历过的数，所以需要一个索引去记录遍历到[1,n]的那个数字了）
2. 终止条件：存下来的path大小已经满足k了
3. 单层递归的逻辑：for循环遍历[1,n]，添加单个数字到path中，再递归添加下一个数字（startIndex+1）。
4. 剪枝：其实单层遍历的时候不需要遍历满[1,n]，当遍历到剩下的数字个数已经不足以组成k个的时候已经不需要再遍历了，所以在for循环中，使用i < n - (k - 目前存的个数) + 1，这里+1是因为范围包含了startIndex

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int n, int k, int startIndex) {//当组合大小满足k时放入结果集if (path.size() == k) {result.push_back(path);return;}//遍历[1,n]依次寻找结果集, 遍历到剩余元素个数不足以满足k的时候就可以停了for (int i = startIndex; i <= n - (k - path.size()) + 1;  i ++) {path.push_back(i); //放入ibacktracking(n, k, i + 1); //寻找跟i能满足k的组合，并且传入遍历的起始下标path.pop_back(); //取出i}return;}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

---

二、216. 组合总和 III

题目链接
文章讲解
视频讲解

跟77. 组合 其实就是多了个和的约束，思路是差不多的。并且要注意题目说只用数字1到9。

思路：

1. 递归函数参数以及返回值：参数：n，k，startIndex（每一层递归需要避开已经遍历过的数，所以需要一个索引去记录遍历到[1,n]的那个数字了）
2. 终止条件：path大小满足k的时候终止，判断总和是否为n，是则加入结果集。
3. 单层处理逻辑：for循环遍历[1,9]，添加单个数字到path中，再递归添加下一个数字（startIndex+1）。
4. 剪枝：跟77. 组合 一样，for循环中只需要到i < n - (k - 目前存的个数) + 1，并且总和大于n了也可以直接返回，不需要再遍历了。

代码如下：

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking (int k, int n, int sum, int startIndex) {if (sum > n) return; //剪枝，超过目标总和了直接返回if (path.size() == k) { //组合大小满足的就要返回，没必要继续下去了if (sum == n) result.push_back(path); //组合大小满足，总和也满足才加入结果集return;}//遍历[1,n]依次寻找结果集, 遍历到剩余元素个数不足以满足k的时候就可以停了，题目要求只使用数字19for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i ++) {sum += i;path.push_back(i);backtracking(k, n, sum, i + 1);//寻找跟i能满足k的组合，并且传入遍历的起始下标和目前的总和path.pop_back();sum -= i;}return;}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return result;}
};

---

三、17. 电话号码的字母组合

题目链接
文章讲解
视频讲解

思路：
需要有一个数组来存下每个数字对应的字母，用一个string[]，用下标对应数字，string对应字符串。

递归思路：

1. 递归函数参数以及返回值：参数：digits，Index（这个索引是告诉递归函数遍历到了digits的那个数字）
2. 终止条件：当遍历完digits时终止，将目前存的string放入结果集。
3. 单层处理逻辑：for循环遍历digits[Index]对应的字符串，添加单个字母到string中，再递归添加下一个数字对应的字母（index+1）。

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 (string &digits, int index) {if (index == digits.size()) { //当遍历完digits字母时终止并保存结果result.push_back(s);return;}int digit = digits[index] - '0'; //将index指向的数字转为intstring letters = letterMap[digit]; //取出数字对应的字母集for (int i = 0; i < letters.size(); i++) { //遍历子母集获取字母组合s.push_back(letters[i]);backtracking(digits, index + 1); //递归，index+1因为下一层是处理digits的下一个字母了s.pop_back(); //回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};

---

总结

今天主要学习了回溯算法的理论和其中解决组合类的题目。

• 回溯算法是一种纯暴力的方法，嵌套多个for循环
• 回溯法解决的问题都可以抽象为树形结构
• 组合类的题目需要使用一个索引去告诉函数遍历到哪里了

明天继续加油！