一、前言
参考文献：代码随想录
今天的还是回溯算法，主要用到了昨天的回溯组合方法和巧妙思路方法，让我们继续为算法打基础吧！
二、组合总和|||
1、思路：
这一题和昨日的组合没啥太大区别只是遍历的范围变为了固定的1~9，所以只需要在for循环中做做手脚即可。
（1）首先还是确定返回值和参数，这里和昨天的一样，返回void，参数三个参数，组合大小，总和大小，以及开始位置
void backtracking(int k, int n, int Instart) （2）接着就是终止条件了，这个需要判断两个条件，以来确认是否符合要求
if (sum == n && path.size() == k) {
result.push_back(path);
return;
}长度和大小要符合要求。
（3）接着就是for循环和递归回溯了，最开始的版本是
for (int i = Instart; i < 10; i++) {
path.push_back(i);
sum += i;
backtracking(k ,n, i + 1);
// 回溯，重新利用
path.pop_back();
sum -= i;
这里就没有涉及到剪枝的操作，而只是全部暴力递归了，然而我们发现sum>n时，就可以提前回溯了，因为后面的肯定不符合要求了。
for (int i = Instart; i < 10 - (k - path.size()) + 1; i++) {
path.push_back(i);
sum += i;
// 剪枝操作，只要sum大于n就可以直接剪掉了
if (sum > n) {
path.pop_back();
sum -= i;
return;
}
backtracking(k ,n, i + 1);
// 回溯，重新利用
path.pop_back();
sum -= i;
}2、整体代码如下：
class Solution {
private:
vector<int> path; // 存储单个组合
vector<vector<int>> result; // 返回结果
int sum; // 统计是否等于n
void backtracking(int k, int n, int Instart) {
if (sum == n && path.size() == k) {
result.push_back(path);
return;
}
for (int i = Instart; i < 10 - (k - path.size()) + 1; i++) {
path.push_back(i);
sum += i;
// 剪枝操作，只要sum大于n就可以直接剪掉了
if (sum > n) {
path.pop_back();
sum -= i;
return;
}
backtracking(k ,n, i + 1);
// 回溯，重新利用
path.pop_back();
sum -= i;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return result;
}
};三、电话号码的字母组合
1、思路:
这个题目，我根据我的印象做了，但是出不来，主要是对c++的STL不熟悉所以导致出不来结果，然后只能请问GPT教授了：
（1）首先这个题目也是利用回溯，即递归里面套循环，这里我们的返回值和参数如下：
void backtracking(string digits, int startI, int startJ, vector<string> s)其实这里面的startJ可以省略，因为他一直是从0开始的，从头开始遍历，找到组合项，digits就是需要按的按键，startI为按键的开始位置，s就是按键所对应的数字了
（2）终止条件，也很普遍，这里就不多说了
if (path.size() == digits.size()) {
result.push_back(path);
return;
}（3）接着就是循环和递归了，这里面略微有些技巧，但是不多
for (int i = startI; i < digits.size(); i++) {
// 判断这个按键包含数字的多少
int digit = digits[i] - '2';
for (int j = startJ; j < s[digit].size(); j++) {
path.push_back(s[digit][j]);
backtracking(digits, i + 1, 0, s);
path.pop_back();
}
}一共嵌套两层循环，第一层是按键的位置，第二层是按键包含的字母，就开始递归，回溯了。
2、整体代码如下：
class Solution {
private:
string path;
vector<string> result;
void backtracking(string digits, int startI, int startJ, vector<string> s) {
if (path.size() == digits.size()) {
result.push_back(path);
return;
}
for (int i = startI; i < digits.size(); i++) {
int digit = digits[i] - '2';
for (int j = startJ; j < s[digit].size(); j++) {
path.push_back(s[digit][j]);
backtracking(digits, i + 1, 0, s);
path.pop_back();
}
}
}
public:
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) {
return result;
}
vector<string> s = {
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
backtracking(digits, 0, 0, s);
return result;
}
};今日学习时间：1.5小时
leave message:
The boundless forest sheds its leaves shower by shower; the endless river rolls its waves hour after hour.
无边落木萧萧下，不尽长江滚滚来。
