题目1：216 组合总和Ⅲ
题目链接：216 组合总和Ⅲ
题意
找出相加之和为n的k个数的组合 数字只可使用1~9之间的数（包括 1 9）且每个数字只能使用1遍
题目中有两个限制条件：1）k个数 2）k个数的和为n 所以最终满足条件一个的组合一定要先判断是k个数，然后再计算这k个数的和为n，只有这样才是
回溯
回溯三部曲：
1）参数和返回值
2）终止条件 叶子节点 和为n的 k个数放入数组中
3）单层递归逻辑
sum不是参数
代码
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int k,int n,int startIndex){//终止条件int sum = 0;if(path.size()==k){for(int i=0;i<k;i++){sum += path[i];}if(sum==n){result.push_back(path);}return;}//单层搜索逻辑for(int i=startIndex;i<=9;i++){path.push_back(i);backtracking(k,n,i+1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1);return result;}
};Sum作为参数
伪代码
代码
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int targetSum,int k,int Sum,int startIndex){//终止条件if(path.size()==k){if(Sum==targetSum)result.push_back(path);return;}//单层搜索逻辑for(int i=startIndex;i<=9;i++){Sum += i;path.push_back(i);backtracking(targetSum,k,Sum,i+1);Sum -= i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(n,k,0,1);return result;}
};剪枝
剪枝1
剪枝2
代码
class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int targetSum,int k,int Sum,int startIndex){if(Sum>targetSum) return;//剪枝1 //终止条件if(path.size()==k){if(Sum==targetSum)result.push_back(path);return;}//单层搜索逻辑for(int i=startIndex;i<=9-(k-path.size())+1;i++){Sum += i;path.push_back(i);backtracking(targetSum,k,Sum,i+1);Sum -= i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(n,k,0,1);return result;}
};- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
题目2：17 电话号码的字母组合
题目链接：17 电话号码的字母组合
题意
字符串中仅包含2-9，每个数字代表的字母和电话按键相同，返回其能表示的所有的字母组合
操作两个集合
回溯
回溯三部曲：
1）参数和返回值
2）终止条件 叶子节点收获结果
3）单层递归逻辑
代码
class Solution {
public://数字与字符串映射 将数字下标对应到字母字符串 2->abcstring letterMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};string path ;//存放单个结果vector<string> result;//存放结果集void backtracking(string& digits,int index){//这里注意& //终止条件 index遍历到最后一个数字之后 存放结果if(index==digits.size()){result.push_back(path);return;}//单层递归逻辑//取出digits数字字符串中的单个字符 并将该字符转换为数字int digit = digits[index] - '0';//将该数字映射为字符串string letter = letterMap[digit];for(int i=0;i<letter.size();i++){path.push_back(letter[i]);backtracking(digits,index+1);//递归 将下标往后移动一个，指向下一个数字path.pop_back();//回溯}}vector<string> letterCombinations(string digits) {path.clear();result.clear();//这里的result一定要clear 不然后面的测试用例""会报错if(digits.size()==0) return result;backtracking(digits,0);//从数字字符串中的第1个字符开始遍历return result;}
};- 时间复杂度: O(3^m * 4^n)，其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数
- 空间复杂度: O(3^m * 4^n)
