代码随想录算法训练营
Day22 代码随想录算法训练营第 22 天 |LeetCode77. 组合 LeetCode 216.组合总和III LeetCode17.电话号码的字母组合
目录
前言
LeetCode77. 组合
LeetCode216.组合总和III
LeetCode17.电话号码的字母组合
一、基础
1、回溯可以解决什么问题
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则排列，有几种排列方式
棋盘问题：N皇后，解数独
2、回溯法
（1）回溯法解决的问题都抽象为树形结构，是一棵高度有限的树（N叉树）
（2）回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
（3）模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
二、LeetCode77. 组合
1.题目链接
2.思路
（1）参数：start是每一层搜索起始位置
（2）边界：组合凑够k个元素，存答案，返回
（3）单层递归：
从start开始这层的搜索
1）当前点存入组合
2）递归下一层
3）回溯，将当前点弹出
3.题解
class Solution {
public:
void add_path(int n,int k,int start,vector<vector<int>>& res,vector<int> &path)
{
if(path.size()==k)
{
res.push_back(path);
return;
}
for(int i=start;i<=n;i++)
{
path.push_back(i);
add_path(n,k,i+1, res,path);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
add_path(n,k,1,res,path);
return res;
}
};
（4）剪枝优化
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
如果i太靠后，组合凑不出k个数
三、LeetCode 216.组合总和III
1.题目链接
2.思路
和上面模板题差不多，区别有三个
（1）类成员加一个sum
（2）边界条件：长度为K,但是要比较和是不是n
（3）单层递归时，每轮循环sum加当前数字，回溯时减掉
3.题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int sum = 0;
void solve(int n, int k, int start) {
if (path.size() == k) {
if (sum == n)
res.push_back(path);
return;
}
for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {
path.push_back(i);
sum += i;
solve(n, k, i + 1);
sum -= i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
solve(n, k, 1);
return res;
}
};
四、LeetCode17.电话号码的字母组合
1.题目链接
2.思路
（1）数字和字母的对应关系：
- 我选择用字符串数组映射，下标表示数字，数组元素为数字对应的字符串（有点哈希表的感觉）
- 为了让下标2对应"abc"，我将下标0和1对应成空字符串，从下标2开始映射
（2）存放答案：
用字符串数组存放最后的答案，用字符串存放每一条路径（组合）
（把模板里面数组存放路径改成字符串存放路径）
（3）递归
1）返回值和参数 - 返回值选择void，写递归容易
- 参数包括：
- 表示数字的字符串digits；
- index表示本轮讨论digits当中下标为index的元素；
- n是digits的长度，没有也行，但是为了避免重复的调用digits.size()浪费时间，我还是加上了
2）边界条件：路径长度（组合大小）等于digits，将组合存入答案
3）单层递归
① 获取当前讨论的数字：从digits取出，并转换成数字
② 求当前讨论的数字映射的字符串长度，即为len
③ for循环讨论这个数字映射的字符串中哪一个字符应该放进组合：
将字符加入路径
递归调用求解digits里面下一个数字（index+1）
将讨论过的字符取出
3.题解
class Solution {
public:
vector<string> s = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string path;
void func(string digits, int index, int n) {
if (path.size() == n) {
res.push_back(path);
return;
}
int number = digits[index] - '0'; // 现在讨论的是字符串中那个数字
int len = s[number].size(); // 现在讨论的数字对应字符串有多少个字符
for (int i = 0; i < len; i++) {
path += s[number][i];
func(digits, index + 1, n);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
int n = digits.size();
if (n == 0)
return res;
func(digits, 0, n);
return res;
}
};
标签：digits,组合,int,res,随想录,vector,字母组合,path From： https://blog.csdn.net/2301_79647020/article/details/140653766