代码随想录二刷|回溯1
回溯
组合问题
方法
组合
题干
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路
（1）定义全局变量数组，作为存放组合的数组和存放最终答案的数组
（2）如果组合长度为k，加入答案，返回
（3）从起始的index出发，直到n，一次放入组合，递归调用下一个index，再弹出组合里面的index
class Solution {
public:
vector<vector<int>>res;
vector<int>ans;
void f(int n,int k,int index){
if(ans.size()==k){
res.push_back(ans);
return;
}
// if(index+k>n){
// return;
// }
for(int i=index;i<=n;i++){
ans.push_back(i);
f(n,k,i+1);
ans.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
f(n,k,1);
return res;
}
};
组合的优化
题干
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路
优化点：遍历的终点从n改成n-(k-ans.size())+1
因为如果剩下的元素不足够填满组合，就停下来
（n = 4，k = 3， 目前已经选取的元素数为0（ans.size为0），现在的index是1，n - (k - index) + 1 即 4 - ( 3 - 1) + 1 = 3，也就是说，组合的第一个匀速可以是1或2或3）
class Solution {
public:
vector<vector<int>>res;
vector<int>ans;
void f(int n,int k,int index){
if(ans.size()==k){
res.push_back(ans);
return;
}
for(int i=index;i<=n-(k-ans.size())+1;i++){
ans.push_back(i);
f(n,k,i+1);
ans.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
f(n,k,1);
return res;
}
};
组合之和
题干
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
思路
（1）结束条件：组合长度到k的时候，如果组合之和是n，那么存答案。无论组合之和是否为n，只要长度到k，都要返回
（2）遍历： 从起始值到9，依次加入组合，递归调用下一个值，将现在的元素从组合拿走
class Solution {
public:
vector<vector <int>>res;
vector<int> ans;
void f(int k,int n,int index){
if(ans.size()==k){
int s=0;
for(int j=0;j<k;j++){
s+=ans[j];
}
if(s==n)res.push_back(ans);
return;
}
for(int i=index;i<=9;i++){
ans.push_back(i);
f(k,n,i+1);
ans.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
f(k,n,1);
return res;
}
};