题目：
找出所有相加之和为 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]]
解题思路
1. 回溯算法
组合问题用回溯算法解决，将该题想想成一个9叉树。
1-9的9叉树
9叉树的遍历可以参考二叉树，代码如下：
private void dfs(一些参数) {
//递归必须要有终止条件
if ("终止条件") {
//1，执行一些操作（可有可无，视情况而定）
return;
}
//通过循环，分别遍历9个子树,二叉树是分别遍历左右节点
for (int i = 0; i <= 9; i++) {
//2，一些操作，可有可无，视情况而定
//递归
dfs(一些参数);
//3，一些操作，可有可无，视情况而定
}
}
递归主要分为递与归的过程，也就是往下传递与往回走，以斐波那契数列为例。
斐波那契数列
所以本题也一样，往下传递的时候我们要把当前节点的值加入到一个集合中，并且用n减去当前节点的值，返回的时候再把它给移除掉就行了。那么终止条件是什么呢，就是集合中的size等于k，并且n等于0。
代码
import java.util.ArrayList;
import java.util.List;
/**
* 组合总和3
*/
public class CombinationSum3 {
public List<List<Integer>> combinationSum3(int k, int n){
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), k, 1, n);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n){
//终止条件,当加入list的数量==k，或者n==0,不用找了,找到合适的了
if (list.size() == k && n == 0) {
res.add(new ArrayList<>(list));
return;
}
//注意这里，因为不能有重复的集合以及集合中不能有重复的数字，所以这里的i不能从0开始，
// 要从上一个选择之后的下一个值开始
for (int i=start; i<=9; i++){
//递过程
list.add(i);
//递归
dfs(res, list, k, i+1, n-i);
//返回过程
list.remove(list.size()-1);
}
}
}
