官方网站下载抖音,北京通州网站设计公司,网站建设图片代码,南京疾控最新通告今天216.组合总和III 题目链接/文章讲解#xff1a;链接地址 视频讲解#xff1a;链接地址 代码思路#xff1a;回溯三部曲#xff1a; 1.确定函数参数#xff1a;n,k,sum,startIndex; 2.结束条件#xff0c;path k,并且如果sumn 结束递归 3.递归回溯逻辑。
class Solution…216.组合总和III 题目链接/文章讲解链接地址 视频讲解链接地址 代码思路回溯三部曲 1.确定函数参数n,k,sum,startIndex; 2.结束条件path k,并且如果sumn 结束递归 3.递归回溯逻辑。
class Solution {vectorint path;vectorvectorint result; private:void back_tracking(int k, int n, int startIndex, int sum) {if (path.size() k) {if (sum n) result.push_back(path);return;}for (int i startIndex; i 9; i) {sum i;path.push_back(i);back_tracking(k, n, i 1, sum);sum - i;path.pop_back();}}public:vectorvectorint combinationSum3(int k, int n) {int sum;back_tracking(k, n, 1, sum);return result;}
};17.电话号码的字母组合 题目链接/文章讲解链接地址 视频讲解链接地址 代码思路传入参数输入的数字第几个数字的索引 结束条件第几个数字的索引等于输入数字的长度 递归回溯先找到创建的数字Map的索引然后找到对应数字下的字符进行遍历递归。
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};string s;vectorstring result; void back_traking(string digits, int index) {if (index digits.size()) {result.push_back(s);return;}//转数字int numIndex digits[index] - 0;//映射数字对应的字符string stringNum letterMap[numIndex];for (int i 0; i stringNum.size(); i) {s.push_back(stringNum[i]);back_traking(digits, index 1);s.pop_back();}}
public:vectorstring letterCombinations(string digits) {if (digits ) return result;back_traking(digits,0);return result;}
};
