回溯
组合问题
方法
组合
题干
给定两个整数 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;}
};
