代码随想录算法训练营第十九天 | LeetCode77.组合、LeetCode216.组合总和III、LeetCode17.电话号码的字母组合
代码随想录算法训练营第十九天 | LeetCode77.组合、LeetCode216.组合总和III、LeetCode17.电话号码的字母组合
01-1 回溯算法理论基础
相关资源
文章讲解：回溯算法理论基础
视频讲解：回溯法精讲
回溯法是什么：回溯函数也就是递归函数，指的都是一个函数。回溯是递归的副产品，只要有递归就会有回溯。
回溯法的效率：暴力搜索，穷举
回溯法解决的问题：组合问题、切割问题、子集问题、排列问题、棋盘问题
回溯法解决的问题都可以抽象为树形结构，回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
回溯法模板：
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
02-1 LeetCode77.组合
相关资源
题目链接：77. 组合
文章讲解：组合
视频讲解：学透回溯算法-组合问题（对应力扣题目：77.组合）、学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）
题目：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
第一想法：照猫画虎，组合问题每次就取当前元素后面的范围中k-1的数的组合
实现：
class Solution {
public:vector<vector<int>> result;void backtracking(int begin, int n, int k, vector<int>& rec){if(k==0){result.push_back(rec);return;}for(int i = begin;i <= n;i++){if(n-i+1>=k){rec.push_back(i);backtracking(i+1,n,k-1,rec);rec.pop_back();}}}vector<vector<int>> combine(int n, int k) {vector<int> rec;backtracking(1,n,k,rec);return result;}
};
看完代码随想录之后的想法：和录哥思路一致
收获：回溯算法的剪枝操作一般在循环的边界上做文章
ToDo：复习
02-2 LeetCode216.组合总和III
相关资源
- 题目链接：216. 组合总和 III
- 文章讲解：组合总和III
- 视频讲解：LeetCode：216.组合总和III
题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
第一想法：和前面组合的题目很类似
实现：
class Solution {
public:vector<vector<int>> result;vector<int> rec;void backtracking(int begin, int k, int n){if(n==0&&k==0){result.push_back(rec);return;}if(n<0){return;}for(int i = begin; i <= 9; i++){rec.push_back(i);backtracking(i+1, k-1, n-i);rec.pop_back();}return;}vector<vector<int>> combinationSum3(int k, int n) {backtracking(1,k,n);return result;}
};
看完代码随想录之后的想法：思路一致，但剪枝更加彻底，一方面是超过了目标和，另一方面是剩余元素个数小于k
ToDo：复习，优化剪枝
02-3 LeetCode17.电话号码的字母组合
相关资源
题目链接：17. 电话号码的字母组合
文章讲解：电话号码的字母组合
视频讲解：LeetCode：17.电话号码的字母组合
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
第一想法：很暴力的方法我知道，无非就是字符串中每一个字符对应一个集合，然后集合里的元素互相匹配，但是不知道怎么用代码实现
看完代码随想录之后的想法：和前面组合问题不能，树中每层节点为新的集合，所以index应该指向新的字母进行递归
实现：
class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> result;string s;void backtracking(string digits, int index, string s){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);s.pop_back();}return;}vector<string> letterCombinations(string digits) {if (digits.size() == 0) {return result;}backtracking(digits,0,"");return result;}
};
ToDo：复习！这道题没啥思路