代码随想录算法训练营第二十二天

题目：216. 组合总和 III

这道题和上道题非常类似，大体框架一样只不过修改一下终止条件而已 值得注意的是其中的剪枝条件的设置  一是靠现有的元素和已经大于目标和的话就提前终止，另一个是其中循环那个剪枝可以记住  i <= n - (k - path.size()) + 1

完整代码如下：

class Solution {
private:vector<vector<int>> result; // 存放结果集vector<int> path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum > targetSum) { // 剪枝操作return; }if (path.size() == k) {if (sum == targetSum) result.push_back(path);return; // 如果path.size() == k 但sum != targetSum 直接返回}for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝sum += i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯}}public:vector<vector<int>> combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear();   // 可以不加backtracking(n, k, 0, 1);return result;}
};

题目：17. 电话号码的字母组合

首先得定义一个数组 把数字和字母做映射

然后是从每个数字对应的字母集合里取字母 注意不能在同一个字母集合里面取多个，这是不满足题意的 因此不能用前天的组合的那套方法  只能把每个数字对应的字母集合放入vector容器里 然后从每个索引里依次取一个字母来组成一个集合

然后单层逻辑一定要自己分析出树形图之后 写单层递归逻辑   其中横向 是用for循环控制的 用于从每一个字母集合里面取数字  然后递归是控制纵向的用于从不同的集合里取数字。

自己写的整体代码如下：

class Solution {
public:vector<string> table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> result;vector<char> path;void backtracking(vector<string>& merge_Str, int k, int index, vector<char>& path) {if (path.size() == k) {string temp;for (char s : path) {temp += s;}result.push_back(temp);return;}for (int i = 0; i < merge_Str[index].size(); i++) { path.push_back(merge_Str[index][i]);backtracking(merge_Str, k, index + 1, path);path.pop_back();} }vector<string> letterCombinations(string digits) {if (digits == "") return result;vector<string> merge_Str;for (char s : digits) {merge_Str.push_back(table[s - '0']) ;}backtracking(merge_Str, digits.size(), 0, path);return result;}
};

代码随想录的代码如下：

// 版本一
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 s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0';        // 将index指向的数字转为intstring letters = letterMap[digit];      // 取数字对应的字符集for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了s.pop_back();                       // 回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};