216. Combination Sum III
problem description
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.
Note:
All numbers will be positive integers. The solution set must not contain duplicate combinations.
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]]
algorithm thought
组合问题,直接用回溯法解决,中间加入剪枝,如果sum已经大于n了,就可以不用继续往下求解了
code
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> tmp;
help(res,k,n,tmp,0,1);
return res;
}
void help(vector<vector<int>>&res,int k,int n,vector<int>&tmp,int sum,int pos){
if(tmp.size()==k){
if(sum==n){
res.push_back(tmp);
}
return;
}
for(int i=pos;i<10;++i){
//cout<<pos<<'-'<<i<<' ';
if(sum+i>n)
return;
tmp.push_back(i);
help(res,k,n,tmp,sum+i,i+1);
tmp.pop_back();
}
}
};
algorithm analysis
遍历求解3个数的组合,时间复杂度 O(C(9,k))-> O(9^k), 空间复杂度: k
Last updated