Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
题目:从1-9个数字中,找出k个数,是k个数的和为n,
返回所有k个数字所有的组合,每一个组合中k个数字都是不相同的.
思路:
深度优先搜索dfs+剪枝,
leetecode上的大部分递归题目,都会利用这种方式的写法
===============
code:
时间复杂度:O(n!),会出现n!总组合
空间复杂度:O(n),递归会n层
class Solution {
public:
void help_cbs3dfs(int k,int n,int level,vector<int> &out,vector<vector<int>> &re){
//@k,每一组合的数量
//@n,
//@level,从何处开始搜索
//@out,保存搜索路径
//@re,最终结果
if(n<) return;
if(n== && (int)out.size()==k) re.push_back(out);
for(int i = level;i<=;i++){
out.push_back(i);
help_cbs3dfs(k,n-i,i+,out,re);
out.pop_back();
}
}
vector<vector<int>> combinationSum3(int k,int n){
vector<vector<int>> re;
vector<int> out;
help_cbs3dfs(k,n,,out,re);
return re;
}
};
==