找出所有相加之和为 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]]

答案：

 1public List<List<Integer>> combinationSum3(int k, int n) {
 2    List<List<Integer>> ans = new ArrayList<>();
 3    combination(ans, new ArrayList<Integer>(), k, 1, n);
 4    return ans;
 5}
 6
 7private void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
 8    if (comb.size() == k && n == 0) {
 9        List<Integer> li = new ArrayList<Integer>(comb);
10        ans.add(li);
11        return;
12    }
13    for (int i = start; i <= 9; i++) {
14        comb.add(i);
15        combination(ans, comb, k, i + 1, n - i);
16        comb.remove(comb.size() - 1);
17    }
18}

解析：

关于组合这已经是第3道了，前面有讲过95，组合总和，96，组合总和 II，其实这题理解起来不难，主要是回溯算法，代码第14行添加当前值i，第16行进行回溯，就是把i给移除。我们再来看一种解法

 1private List<List<Integer>> res = new ArrayList<List<Integer>>();
 2
 3public List<List<Integer>> combinationSum3(int k, int n) {
 4    findCombo(k, n, 1, new LinkedList<>());
 5    return res;
 6}
 7
 8public void findCombo(int k, int n, int start, List<Integer> list) {
 9    if (k == 1) {
10        if (n < start || n > 9)
11            return;
12        list.add(n);
13        res.add(list);
14        return;
15    }
16    for (int i = start; i <= n / k && i < 10; i++) {
17        List<Integer> subList = new LinkedList<>(list);
18        subList.add(i);
19        findCombo(k - 1, n - i, i + 1, subList);
20    }
21}

这题解法和第一题有异曲同工之妙，只不过这题没有回溯，如果不合适则在第11行直接return掉。第10行如果n<start，说明n已经添加在list中，不能有重复的，所以直接return。第16行其实也可以改为for(int i=start;i<10;i++)，但实际上上面代码多了一个i<=n/k的判断，这样效率会更高一些，减少一些不必要的计算。注意这里的第17行，subList每次循环都会新建，新建之后和原来的list没有任何关系。