代码随想录算法训练营Day25|216. 组合总和 III、17. 电话号码的字母组合
216. 组合总和 III
与「77.组合」类似，但区别在于题干要求的变化：
- 只使用数字1到9：遍历范围说明N叉树的宽度，这说明递归每层遍历的上限即为9。
- 每个数字 最多使用一次：不包含重复的数字， 这点与「77.组合」保持一致。
因为是求总和，终止条件添加一个与总和相关的限制即可。
递归函数添加参数int sum用来记录「剩余未满足的差值」，每找到一个值便减去，直到差值变为0。
if (path.size() == k) {
if (sum == 0) res.push_back(path);
return;
}
另外也可以通过差值进行剪枝：当仍然在进行递归时，差值已经为负值（满足和要求，但组合数个数未满足），这时停止继续进行递归：
if (sum < 0) return;
完整代码如下：
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
int sum = n;
backtracking(k, n, sum, 1);
return res;
}
void backtracking(int k, int n, int sum, int startIndex) {
if (path.size() == k) {
if (sum == 0) res.push_back(path);
return;
}
if (sum < 0) return;
for (int i = startIndex; i <= 9; i++) {
path.push_back(i);
backtracking(k, n, sum - i, i + 1);
// 回溯过程
path.pop_back();
}
}
private:
vector<vector<int>> res;
vector<int> path;
};
17. 电话号码的字母组合
与之前回溯问题的区别在于：之前组合问题递归时遍历范围即为递归的搜索范围；但这次的搜索范围是确定的（针对不同的数字），递归范围和搜索范围不一致。
class Solution {
public:
vector<string> letterCombinations(string digits) {
res.clear();
path.clear();
if (digits == "") return res;
backtracking(digits, 0);
return res;
}
void backtracking(string& str, int startIndex) {
if (startIndex == str.size()) {
res.push_back(path);
return;
}
if (str[startIndex] == '2') {
// 分三种情况讨论
path += 'a';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'b';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'c';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '3') {
// 分三种情况讨论
path += 'd';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'e';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'f';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '4') {
// 分三种情况讨论
path += 'g';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'h';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'i';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '5') {
// 分三种情况讨论
path += 'j';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'k';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'l';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '6') {
// 分三种情况讨论
path += 'm';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'n';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'o';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '7') {
// 分三种情况讨论
path += 'p';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'q';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'r';
backtracking(str, startIndex + 1);
path.pop_back();
path += 's';
backtracking(str, startIndex + 1);
path.pop_back();
} else if (str[startIndex] == '8') {
// 分三种情况讨论
path += 't';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'u';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'v';
backtracking(str, startIndex + 1);
path.pop_back();
} else {
// 分三种情况讨论
path += 'w';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'x';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'y';
backtracking(str, startIndex + 1);
path.pop_back();
path += 'z';
backtracking(str, startIndex + 1);
path.pop_back();
}
}
private:
vector<string> res;
string path;
};
优化
①尝试使用字符集去映射数字对应的字符
建立字符映射表，我们用二维数组进行实现：
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
因为条件是字符串的形式，处理后作为下标正好与对应的string相映射。这样遍历流程就不会涉及到具体的数据内容。
int index = digits[startIndex] - '0';
string letters = letterMap[index];
另外可以将字符串视为容器vector，使用push_back()、pop_back()进行处理，完整代码如下：
class Solution {
public:
vector<string> letterCombinations(string digits) {
res.clear();
str.clear();
if(digits == "") return res;
else backtracking(digits, 0);
return res;
}
void backtracking(string& digits, int startIndex) {
if (startIndex == digits.size()) {
res.push_back(str);
return;
}
// 获取字符对应的字母选项
int index = digits[startIndex] - '0';
string letters = letterMap[index];
for (int i = 0; i < letters.size(); i++) {
str.push_back(letters[i]);
backtracking(digits, startIndex + 1);
str.pop_back();
}
}
private:
// 定义的映射数组
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
vector<string> res;
string str;
};