摘要：题目要求输入和，找到所有个不同数字的组合，这些组合中数字的和为参考，解答这是一道典型的的题目，通过递归的方式记录尝试的节点，如果成功则加入结果集，如果失败则返回上一个尝试的节点进行下一种尝试。
题目要求
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]]
输入k和n，找到所有k个不同数字的组合，这些组合中数字的和为n
参考Combination Sum I ，Combination Sum II
解答
这是一道典型的backtracking的题目，通过递归的方式记录尝试的节点，如果成功则加入结果集，如果失败则返回上一个尝试的节点进行下一种尝试。
public List> combinationSum3(int k, int n) {
List> result = new ArrayList>();
combinationSum3(k,n,1,result, new ArrayList());
return result;
}
public void combinationSum3(int k, int n, int startNumber, List> result, List current){
if(k==0 && n==0){ result.add(new ArrayList(current)); return;}
if(k==0 || n<0) return;
for(int i = startNumber ; i<=9 ; i++){
if(i>n){
break;
}
current.add(i);
combinationSum3(k-1, n-i, i+1, result, current);
current.remove(current.size()-1);
}
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67448.html
