首页 > 代码库 > Leetcode题解(4):L216/Combination Sum III
Leetcode题解(4):L216/Combination Sum III
L216: Combination Sum III
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.
Ensure that numbers within the set are sorted in ascending order.
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]]
解题思路:递归,注意一些条件的处理,避免不必要的处理
class Solution {
public:
bool combine(int min, int k, int n, vector<int> vec, vector<vector<int>>& result){
if(n<min*k) //更确切的。能够用等差数列公式算出最大值最小值
return false;
if(n>9*k)
return true;
if(k==1)
{
vec.push_back(n);
result.push_back(vec);
return true;
}
for(int i=min;i<=9;i++)
{
vec.push_back(i);
bool rt = combine(i+1, k-1,n-i, vec, result);
vec.pop_back();
if(!rt)
break;
}
return true;
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> vec;
combine(1,k,n,vec,result);
return result;
}
};
Leetcode题解(4):L216/Combination Sum III
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。