找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。(回溯思想)

找出所有相加之和为 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 class Solution {
 2     public List> combinationSum3(int k, int n) {
 3         List> result = new ArrayList<>();
 4         for(int i=0;i < result.size();i++){
 5             List list = new ArrayList<>();
 6             List re = digui(i,list,n,k);
 7             if(re !=null){
 8                 result.add(re);
 9             }
10         }
11         return result;
12     }
13 
14     List digui(int c,List a,int n,int k){
15         int b;
16         if(a.size() == 0){
17             b = c;
18             a.add(b);
19             return digui(c,a,n,k);
20         }else{
21             b = a.get(a.size()-1)+1;
22         }
23         
24         int total = 0;
25         for(int aa:a){
26             total +=aa;
27         }
28         if(total == n){
29             return a;
30         }
31         if(b>9 || total > n ||a.size()>k)
32             return null;
33         a.add(b);
34         return digui(c,a,n,k);
35     }
36 }

 递归不行，要使用回溯进行解决

 1 class Solution {
 2     //结果集
 3     public static List> lists = new ArrayList>();
 4     //临时集
 5     public static List list = new ArrayList();
 6     public List> combinationSum3(int k, int n) {
 7         huisu(1,list,n,k,0,0);
 8         return lists;
 9     }
10 
11     void huisu(int c,List a,int n,int k,int sum,int index){
12         if(k>n){
13             return;
14         }
15         if(index == k && sum == n){
16             List currentList = new ArrayList();
17             currentList.addAll(list);
18             lists.add(currentList);
19             return;
20         }
21 
22         if(sum > n){
23             return;
24         }
25         for(int i = c;i<= 9; ++i){
26             list.add(i);
27             sum+=i;
28             huisu(i+1,list,n,k,sum,index+1);
29             list.remove(list.size()-1);
30             sum -=i;
31         }
32     }
33 }

递归和回溯的区别

递归：程序调用自身的编程技巧。

　　作为一种程序设计算法，有着广泛应用。需要注意的是，递归结束的条件要控制好。

回溯：是一种算法思想，可以用递归来实现。

　　回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就"回溯"返回，尝试别的路径。

　　回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

回溯思路：

　　基本如下：当前局面下，我们有若干种选择，所以我们对每一种选择进行尝试。如果发现某种选择违反了某些限定条件，此时 return；如果尝试某种选择到了最后，发现该选择是正确解，那么就将其加入到解集中。
　　在这种思想下，我们需要清晰的找出三个要素：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。

回溯算法框架：

 1 result = []
 2 def backtrack(路径, 选择列表):
 3     if 满足结束条件:
 4         result.add(路径)
 5         return
 6     
 7     for 选择 in 选择列表:
 8         做选择
 9         backtrack(路径, 选择列表)
10         撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

递归与回溯的区别

递归是一种算法结构。递归会出现在子程序中，形式上表现为直接或间接的自己调用自己。典型的例子是阶乘，计算规律为：n!=n×(n?1)!

回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。例如有求和问题，给定有 7 个元素的组合 [1, 2, 3, 4, 5, 6, 7]，求加和为 7 的子集。累加计算中，选择 1+2+3+4 时，判断得到结果为 10 大于 7，那么后面的 5, 6, 7 就没有必要计算了。这种方法属于搜索过程中的优化，即“剪枝”功能。

用一个比较通俗的说法来解释递归和回溯：
我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。
这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。

参考：https://www.cnblogs.com/fanguangdexiaoyuer/p/11224426.html

　　　https://blog.csdn.net/summer_dew/article/details/8392158

    　　https://blog.csdn.net/a1439775520/article/details/104539875