216. 组合总和 III - 力扣(LeetCode)
思路:
- 使用回溯法,与77. 组合 - 力扣(LeetCode)类似,只是要在收集到
k
个数据时多判断一次,当这k
个数字的和为n
时才会加入结果数组 - 记得要进行回溯
剪枝:
- 当
sum >= n && tmp.size() < k
时可以直接返回,因为已经不符合条件了 - 当剩余数字与
tmp
中已有数字总和不足以达成k
个时可以直接结束循环
我的AC代码
class Solution { public: vector<vector<int>> ans; vector<int> tmp; int sum = 0; void backtracking(int k, int n, int cur) { if(sum > n || (sum == n && tmp.size() < k)) { return; } if(sum == n && tmp.size() == k) { ans.push_back(tmp); return; } int tsize = tmp.size(); for(int i = cur; i <= 9 - (k - tsize) + 1; ++i) { tmp.push_back(i); sum += i; backtracking(k, n, i + 1); sum -= i; tmp.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { backtracking(k, n, 1); return ans; } };
标准答案
class Solution { private: vector<vector<int>> result; // 存放结果集 vector<int> path; // 符合条件的结果 void backtracking(int targetSum, int k, int sum, int startIndex) { if (sum > targetSum) { // 剪枝操作 return; // 如果path.size() == k 但sum != targetSum 直接返回 } 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); // 注意i+1调整startIndex sum -= 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. 电话号码的字母组合 - 力扣(LeetCode)
思路:
- 与216. 组合总和 III - 力扣(LeetCode)和77. 组合 - 力扣(LeetCode)思路都大体类似,需要注意的是此次进行的组合需要一一对应的转换,而且每次循环都是从对应字符串的头部开始进行(因为之前是在同一个集合中,而这次是在不同的集合中),与前两道题需要记录遍历到哪个数字不同,本题的关键是
tmp.size()
,即已经储存的字母的大小,当大小与k
相等时则说明tmp
中所存数据已经符合条件,应当将加入结果数组,而每次应该加入哪个字符串的字母,也要根据tmp.size()
推导得出
剪枝:
- 当
tmp.size() > k
时,返回
我的AC代码
class Solution { public: vector<string> ans; vector<string> v; string tmp; void backtracking(string& digits, int k, string tmp) { if(tmp.size() > k) { return; } if(tmp.size() == k) { ans.push_back(tmp); return; } int tsize = tmp.size(); int scnt = v[(int)(digits[tsize] - 50)].size(); for(int i = 0; i < scnt; ++i) { backtracking(digits, k, tmp + v[(int)(digits[tsize] - 50)][i]); } } vector<string> letterCombinations(string digits) { if(digits.size() == 0) { return ans; } v.push_back("abc");//0 : 2 v.push_back("def"); v.push_back("ghi"); v.push_back("jkl"); v.push_back("mno"); v.push_back("pqrs"); v.push_back("tuv"); v.push_back("wxyz"); int k = digits.size(); backtracking(digits, k , tmp); return ans; } };
标准答案
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指向的数字转为int string 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; } };
Comments NOTHING