第77题. 组合
在单个集合1-n中,寻找所有个数为k的组合。
和所有递归一样,都有三部曲。
- 确定参数与返回值
- 确定终止条件
- 单层逻辑
首先,回溯算法的返回值一般是void,参数依照题目要求而增加,在这一题中,参数有n,k还有startIndex。
终止条件是path的size等于k,将path存放在result中。
单层逻辑就是将该层的值放到path中,然后递归,回溯。
在这一题中,有一个可以剪枝的地方,就是当余下的量已经不能够大于k,那就不需要去递归了。
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; ++i) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
216.组合总和III
在单个集合1-9中,寻找所有个数为k且和为target的组合。
这一题与上题一样,除了终止条件中需要判断和是否为target。多了一个剪枝操作,就是当值已经大于target,直接返回。
class Solution {
public:
int count;
vector<vector<int>> result;
vector<int> path;
void backtracking(int k, int n, int startIndex) {
if (path.size() == k) {
if (count == n)
result.push_back(path);
return;
}
if (count >= n) {
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; ++i) {
count += i;
path.push_back(i);
backtracking(k, n, i + 1);
count -= i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return result;
}
};
17.电话号码的字母组合
这一题是在多个集合中找所有可能的组合。
因此回溯算法的宽度是每个集合里面的个数,回溯算法的深度是集合的个数。
本题还有一个建立数字和字母之间映射的问题,使用string数组来进行映射。
参数是digits与index,index是用来记录遍历第几个集合。
class Solution {
public:
vector<string> result;
string letter;
const string lettermap[10] = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
void
backtracing(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(letter);
return;
}
int digit = digits[index] - '0';
string s = lettermap[digit];
for (int i = 0; i < s.size(); ++i) {
letter.push_back(s[i]);
backtracing(digits, index + 1);
letter.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0)
return result;
backtracing(digits, 0);
return result;
}
};