难度 medium
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解题思路:这道题和77.组合很像,因为这一题目是求解几个数之和,所以使用深度优先搜索时,每深入一层,和需要减去这一层的i值,最后用和n来进行return判断。
代码 t50 s24 java
class Solution {
private List<List<Integer>> res;
private List<Integer> out;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<>();
out = new ArrayList<>();
helper(1, k, n);
return res;
}
public void helper(int cur, int num, int target){
if(out.size()==num){
if(target==0){
ArrayList<Integer> temp = new ArrayList(out);
res.add(temp);
}
return;
}
for(int i=cur; i<=Math.min(9, target); i++){
out.add(i);
helper(i+1, num, target - i);
out.remove(out.size()-1);
}
}
}
代码 t50 s66 cpp
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> out;
helper(k, n, 1, out, res);
return res;
}
void helper(int k, int n, int level, vector<int> &out, vector<vector<int>> &res){
if(n<0) return;
if(out.size()==k && n==0) res.push_back(out);
for(int i=level, i<=9; i++){
out.push_back(i);
helper(k, n-i, i+1, out, res);
out.pop_back();
}
}
};
参考资料:
http://www.cnblogs.com/grandyang/p/4537983.html