算法打卡 Day28（回溯算法）-组合总数 + 组合总数 Ⅱ+ 电话号码的字母组合

Leetcode 17-电话号码的字母组合

题目描述

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

解题思路

class Solution {
public:vector<string> res;string path = "";vector<string> list = {"abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};void backTracking(string s, int startIndex){if (startIndex == s.size()){res.push_back(path);return;}int digits = s[startIndex]-'0'-2;for (int i = 0; i < list[digits].size();i++){path += list[digits][i];backTracking(s, startIndex+1);path.pop_back();//注意字符串移除的方式，不能使用-=}}vector<string> letterCombinations(string digits) {if (digits.size()==0) return {};backTracking(digits,0);return res;}
};

Leetcode 39-组合总数

题目描述

https://leetcode.cn/problems/combination-sum/description/

解题思路

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& candidates, int target, int startIndex, int sum){if (sum == target){res.push_back(path);return;}if (sum >target) return;for (int i = startIndex; i < candidates.size(); i++){path.push_back(candidates[i]);sum+=candidates[i];backTracking(candidates, target, i, sum);path.pop_back();sum-=candidates[i];}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backTracking(candidates,target,0,0);return res;}
};

Leetcode 216-组合总数 Ⅲ

题目描述

https://leetcode.cn/problems/combination-sum-iii/description/

解题思路

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(int k, int n, int startIndex, int sum){if (sum > n) return;//剪枝操作1if (path.size() == k){if (sum == n){res.push_back(path);}return;}for (int i = startIndex; 9-i+1+path.size() >= k; i++){//剪枝操作2.保证剩余的元素个数能满足使组合个数符合k的要求path.push_back(i); sum+=i;backTracking(k, n, i+1, sum);path.pop_back();sum-=i;}}vector<vector<int>> combinationSum3(int k, int n) {backTracking(k,n, 1, 0);return res;}
};