给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
题目意思很明显，k为多少就是要进行多少次for循环，但要是k很大的话，就写不了那么多for循环的代码了，这种时候就需要用到回溯法。
回溯法三部曲
（一）递归函数的返回值以及参数
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
代码如下：
vector<vector<int>> result; // 存放符合条件结果的集合 vector<int> path; // 用来存放符合条件结果
（二）回溯函数终止条件
什么时候到达所谓的叶子节点了呢？
path这个数组的大小如果达到k，说明找到了一个子集大小为k的组合，path存的就是根节点到叶子节点的路径。
代码如下：
if (path.size() == k) {
result.push_back(path);
return;
}
（三）单程搜索的过程
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
代码如下：
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.pop_back(); // 回溯，撤销处理的节点
}
最终这道题的代码如下：
class Solution {
private:
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; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
优化，对其回溯进行剪枝。
每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
优化剪枝后代码如下：
class Solution {
private:
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();
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
相对于组合，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,…,9]。
另外定义一个参数sum，但sum时将path返回。
需要注意的是，在回溯时，sum也要跟着回溯。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum=0;
void backtrack(int n,int k,int startIndex){
if(path.size()==k){
if(sum==n){
result.push_back(path);
}
return;
}
for(int i=startIndex;i<=9;i++){
path.push_back(i);
sum+=i;
backtrack(n,k,i+1);
path.pop_back();
sum-=i;//sum跟着回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtrack(n,k,1);
return result;
}
};
剪枝优化：
如果遍历时sum已经大于n，那就没有继续遍历的必要了，可以对其剪枝。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum=0;
void backtrack(int n,int k,int startIndex){
if(path.size()==k){
if(sum==n){
result.push_back(path);
}
return;
}
for(int i=startIndex;i<=9;i++){
path.push_back(i);
sum+=i;
if(sum>n){//剪枝
path.pop_back();
sum-=i;
return;
}
backtrack(n,k,i+1);
path.pop_back();
sum-=i;//sum跟着回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtrack(n,k,1);
return result;
}
};
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
首先要思考的是如何解决数字和字母的映射问题。这也是很多题目都需要解决的问题。
这里只需要定义一个一维数组即可：
const string letterMap[10]={
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
另外需要注意的是，在从题目给的digits中取数字时，要将string类型转换成int类型。
整体代码如下：
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> res;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
res.push_back(s);
return;
}
int digit = digits[index] - '0'; //-'0'的作用是转换成int类型。
string letters = letterMap[digit];
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) {
if (digits.size() == 0) {
return res;
}
backtracking(digits, 0);
return res;
}
};
暂无评论