Leetcode: 216 组合总和III
经过了昨天组合的题目的学习,这道题比较简单,套用之前的模板就可以
基本思路
- 终止条件,遇到向量的个数一样,并且sum等于n的时候终止。
- 输入变量,n,k,还有起始的idx和基于当前元素之和的sum
- 逻辑就是,按照循环递归下去,注意要对sum值进行回溯。
时间复杂度O(n * 2^n)
空间复杂度O(N)
class Solution {
private:
vector<vector<int>> result;
vector<int> vec;
void traceback(int k, int n, int idx, int sum){
if(vec.size() == k && sum == n){
result.push_back(vec);
return;
}
for(int i = idx; i <= 9; i++){
vec.push_back(i);
sum += i;//计算当前元素之和
traceback(k, n, i+1, sum);//进行递归
sum -= i;//注意sum值的回溯
vec.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
traceback(k, n, 1, 0);
return result;
}
};
减枝优化
1、每个数值的取值范围为1-9,与上题一样的剪枝操作。2、当所有元素之和已经大于n的时候后续就不需要进行递归了。
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i; // 处理
path.push_back(i); // 处理
if (sum > targetSum) { // 剪枝操作
sum -= i; // 剪枝之前先把回溯做了
path.pop_back(); // 剪枝之前先把回溯做了
return;
}
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
Leetcode: 17 电话号码的字母组合
字母和数字的映射
需要先定义一个二维数组来存放映射关系。文章来源:https://www.toymoban.com/news/detail-808979.html
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
基本思路
- 输入:要求的digit和定义一个idx来记录目前遍历到哪个数字了。
- 终止条件,当遍历的数字和digit长度一样的时候。
- 遍历逻辑:首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
string str;
void traceback(string digits, int idx){
if(idx == digits.size()){
result.push_back(str);
return;
}
int digit = digits[idx] - '0'; // 将idx指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
str.push_back(letters[i]); // 处理
traceback(digits, idx + 1); // 递归,注意index+1,一下层要处理下一个数字了
str.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) {
return result;
}
traceback(digits, 0);
return result;
}
};
本题的难点主要在于1、字母表和数字的映射建立和相互转换 2、递归逻辑的梳理文章来源地址https://www.toymoban.com/news/detail-808979.html
到了这里,关于DAY25:回溯算法组合题216、17的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!