找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
分析:本题与1.0也很像,只是多了总和的限制条件,我们可以将这个限制条件放在递归的函数参数中不断更新,同时在总和小于0时直接返回来进行“剪枝”操作
参考代码:
public List> combinationSum3(int k, int n) {
sup(1,k,n);
return ret;
}
List> ret = new ArrayList<>();
LinkedList
private void sup(int index, int k,int n){
if(n<0) return;
if(path.size()==k){
if(n==0){
ret.add(new ArrayList<>(path));
}
return;
}
for(int i=index;i<=9;i++){
path.add(i);
n-=i;
sup(i+1,k,n);
n+=i;
path.removeLast();
}
}
