day 22|77. 组合 216.组合总和III 17.电话号码的字母组合
基础知识：
回溯套路模板：
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
回溯本质上是一个暴力解法。
可以解决的问题包括：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯问题可以抽象为树形结构。
77. 组合
第77题. 组合 | 代码随想录
笔记
链接里讲的非常好。这里标注一下重要的点：
1.组合问题是没有顺序的，所以需要防止结果数组重复，所以程序中严格控制循环的起始位置（startindex）
2.for循环是用来横向遍历的，即从几个数中选择一个数放进一维数组path中；递归是用来纵向遍历的，即从选择后剩下的数中进一步操作。
剪枝操作：
每一次循环的终止点就是保证剩下内容中能够找到n个数，即 n - (k - path.size()) + 1
实操出现问题
向下一层递归的时候应该是当前起始点startindex后一个，所以应该是i+1
代码/比较
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtrack(int n,int k,int startindex){//截止条件：if(path.size()==k){result.push_back(path);return;}//单层逻辑：for(int i=startindex;i<=n-(k-path.size())+1;i++){path.push_back(i);backtrack(n,k,i+1);path.pop_back();}return;}
public:vector<vector<int>> combine(int n, int k) {backtrack(n,k,1);return result;}
};
216.组合总和III
笔记：
与上一个题目的不同点就在于要多一层判断总和的操作。总体代码差不多，同一种套路。
本题目涉及到的剪枝操作除了上一题中的那个条件外，还多了一个当前和大于目标和的剪枝操作。
代码：
class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(int k,int n,int startindex,int sum)//n为目标和{//剪枝操作：如果当前和已经大于目标和了，直接退出if(sum>n)return ;//截止条件：如果path中个数相同，并且当前和与目标和相同if(path.size()==k){if(sum==n) result.push_back(path); return ;}//单层递归：for(int i=startindex;i<=9-(k-path.size())+1;i++){path.push_back(i);backtracking(k,n,i+1,sum+i);path.pop_back();}return;}
public:vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1,0);return result;}
};
17.电话号码的字母组合
17.电话号码的字母组合 | 代码随想录
笔记：
画树状图是非常有用的，怎么把这个问题转化为树状图？很显然，这个问题和上面两个问题是不同的，因为他是在不同集合里面取一个char，所以我们画树状图的时候，每一层的内容是不一样的，每一层的内容是不同数字对应的string，这样就可以画出本题的树状图了。
再回看树状图，事实上本题唯一的区别也就是每一层取的内容不一样，这就是唯一的区别了，再按照套路代码想下来就好。
实操出现问题：
对字符串的操作还是有很多不熟悉的地方：
1.不能在类内使用圆括号初始化，这样编译器会不清楚这是成员变量声明还是成员函数声明。应该使用花括号初始化；
2.字符型变量转为int：int num = digits[i] - '0';
代码：
class Solution {
private:vector<string> m_string = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> result;string path;void backtracking(vector<int> digits,int startindex){//截止条件：如果path.size()和想要长度相同了，将path放入result中if(path.size()==digits.size()){result.push_back(path);return;}//迭代逻辑：string phone=m_string[digits[startindex]];for(int i=0;i<phone.size();i++){path+=phone[i];backtracking(digits,startindex+1);path.pop_back();}return ;}
public:vector<string> letterCombinations(string digits) {vector<int> digits_num;//转换为intfor(int i=0;i<digits.size();i++){int num=digits[i]-'0';digits_num.push_back(num); }backtracking(digits_num,0);return result;}
};
1