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