题目链接：leetcode 17.电话号码的字母组合
文章讲解：代码随想录 17.电话号码的字母组合讲解
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合
思路和解法
题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
想法：
感觉最近刷题质量细下降了，花的时间也不够多，确实自己写了一遍代码，但是总会写出bug，自己还查不出来，需要gpt协助。后面每天的题目必须都自己写熟练，多思考。另外bug总出在小细节上，尤其是一些C++语法的使用上。
今天这道题目，第一个错误就是剪枝条件一开始加错了，所以递归回溯一开始还是不要想着剪枝。第二个bug是终止条件想复杂了，其实就判断path的长度以及是否满足想要的东西就行了，其他情况怎么递归都无所谓，因为不会加入result。剪枝确实还是不要太好想。而且剪枝似乎有很多可以优化的地方，不能全部都想全，只能把最显而易见的剪枝考虑到，否则可能判断的太多反而不好吧。
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
//记录路径之和
int sum;
//递归函数
void backTracking(int k, int n, int startIndex) {
if (path.size() == k && sum == n) {
result.push_back(path);
return ;
}
//递归处理
for (int i = startIndex; i <= 9; i++) {
//剪枝条件
if (n - sum < i) {
break;
}
path.push_back(i);
sum += i;
backTracking(k, n, i + 1);
sum -= i;
path.pop_back();
}
return ;
}
vector<vector<int>> combinationSum3(int k, int n) {
backTracking(k, n, 1);
return result;
}
};
题目链接：leetcode 216.组合总和III
文章讲解：代码随想录 216.组合总和III讲解
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III
思路和解法
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
想法：
感觉最近刷题质量细下降了，花的时间也不够多，确实自己写了一遍代码，但是总会写出bug，自己还查不出来，需要gpt协助。后面每天的题目必须都自己写熟练，多思考。另外bug总出在小细节上，尤其是一些C++语法的使用上。
今天这道题目，第一个错误就是剪枝条件一开始加错了，所以递归回溯一开始还是不要想着剪枝。第二个bug是终止条件想复杂了，其实就判断path的长度以及是否满足想要的东西就行了，其他情况怎么递归都无所谓，因为不会加入result。剪枝确实还是不要太好想。而且剪枝似乎有很多可以优化的地方，不能全部都想全。
class Solution {
public:
//表格
const string letterMap[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
string path;
vector<string> result;
//递归函数
void backTrack(string digits, int index) {
//终止条件
if (path.size() == digits.size()) {
result.push_back(path);
return ;
}
//递归处理过程
string s = letterMap[digits[index] - '0'];
for (int i = 0; i < s.size(); i++) {
path.push_back(s[i]);
backTrack(digits, index + 1);
path.pop_back();
}
return ;
}
vector<string> letterCombinations(string digits) {
path.clear();
result.clear();
if (digits.size() == 0) {
return result;
}
backTrack(digits, 0);
return result;
}
};
