目录
216.组合总和III
前言
相对于上一题组合，本题就是多了一个限制，要找到和为n的k个数，集合已经是固定的[1,……,6]。本题k相当于树的深度，9就是树的宽度。
算法实现
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex){
if (path.size() == k){
if (sum == targetSum) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9; i++){
sum += i;
path.push_back(i); //处理节点
backtracking(targetSum, k, sum, i + 1); //调用递归
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;
}
};剪枝处理
当已选元素总和已经大于n了，那么往后遍历就没有意义了，可以直接剪掉，这部分剪枝可以放在递归开始的地方，也可以放在调用递归之前，但是要在剪枝操作中把回溯操作给做了。还有一部分剪枝是在循环遍历的过程中若当前遍历的元素位置之后剩余的元素全部加入都无法满足k个元素的条件，则可以直接剪枝。剪枝后的代码如下：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex){
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);
if (sum > targetSum){
sum -= i;
path.pop_back(); //剪枝之前先把回溯做了
return;
}
backtracking(targetSum, k, sum, i + 1);
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.电话号码的字母组合
前言
要将电话号码所对应的字母进行组合，主要有以下几个问题：
- 数字和字母如何映射？
- 要是输入两个数字可以两个for循环输出对应的字母组合，三个数字可以三个for循环，以此类推，多个数字叠加的for循环过多。
- 输入“1”，“#”按键等等异常情况
思路
针对数字和字母映射问题，我们可以通过使用map或者创建一个二维数组来实现映射；使用回溯法来解决n个for循环的问题。
算法实现
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 digt = digits[index] - '0'; //将index指向的数字转为int
string letters = letterMap[digt]; //取数字对应的字符集
for (int i = 0; i < letters.size(); i++){
s.push_back(letters[i]);
backtracking(digits, 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;
}
};本题的for循环不像前几题从startIndex开始遍历，因为本题每一个数字代表的是不同集合，是不同集合之间的组合，前几题都是求同一个集合中的组合。
总结
利用回溯法解决问题的时候要多考虑是否能进行剪枝优化处理。
