回溯---组合总和

摘要

你能找出所有相加之和为 n 的 k 个数的组合吗？？？？？？，又是一个递归回溯问题尼！！！！

# 回溯---组合总和

1. 题目描述

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

2. 示例描述

- 示例一
     - 输入：k = 3, n = 7
     - 输出：[[1,2,4]]
   - 示例二
     - 输入：k = 3, n = 9
     - 输出：[[1,2,6], [1,3,5], [2,3,4]]

3. 解题思路

- 这道题目又是一道经典的回溯题目，并且这道题目与[回溯组合一](http://www.geticsen.cn/view/articles/detail/2de237b2-bb27-4837-8ce7-ac462b887705 "回溯组合一")这道题目非常类似，只要会这道题，那么本道题做起来就是信手捏来的题目。但是这里我们应该注意，这里循环的集合变成了一到九。然后题目要求变成了k个数的总和等于n，集合就是一到九直接，并且集合中不出现重复的数据。
   - 这里还是按照回溯步骤的五步法(我自的总结的，大家可以总结自己对这种算法的套路)。首先确定回溯的递归出口，这里的递归出口的条件有两个要求：第一个就是集合中的值的和等于n,并且集合的个数等于k。第二步就是确定递归与回溯的集合，题目以及给出组合中只能出现一到九，所以集合我们也就确定了。第三步就是就是记录本层递归的值，即就是本层的值加入结果集合中，同时集合中的值的和也加上刚才加入的节点的值。第四步就是继续执行递归，也就是继续寻找本层下面其余的集合。第五步就是回溯，因为递归思想中有个回退的步骤，当回溯到本层的时候，应该移除之前在本层的操作，这样就不会 影响本层其他节点的递归了。这样才能达到全局暴力搜索。
   - 下面是具体实现的形式，大家可以对比上一篇文章的代码与这篇文章的代码进行比较，会发现都是按照套路进行写的，大家也可以总结自己的套路，下次遇到这种题目的时候就不会不知所措了。

4. 代码示例

```java
   //定义最终结果结合、集合中每个元素又是一个集合，也就是1到9中的k个数的集合
       //最终1到9的所有k个数的集合的集合就是最终结果
       List<List<Integer>> result = new ArrayList<>();
   
       public List<List<Integer>> combinationSum3(int k, int n) {
           //调用自己写的递归回溯算法
           trackBack(k, n, 1, new ArrayList<>(), 0);
           return result;
       }
   
       //算法的参数定义为什么是这样的呢
       //首先前两个参数不用说了，就是题目的参数
       //后面三个参数解释一下(index参数，就是本层循环到哪个数了，这个数就是控制递归函数持续向下搜索的遍历，直到底层为止，就结束本层递归)
       ///倒数第二个参数就是记录递归过程中，所到达的节点，并且也是最终结果集合的子集的记录者
       //最后一个参数就是记录本次集合总所有值的和。
       public void trackBack(int k, int n, int index, List<Integer> tempResult, int sum) {
           //满足递归出口的条件就把临时结果加入最终结果中
           //这里递归出口的条件不难看出，就是集合集中的和为n,集合的个数为k。
           if (sum == n && tempResult.size() == k) {
               result.add(new ArrayList<>(tempResult));
               return;
           }
           //这里也就是剪枝操作，把已经不满足题目要求的递归提前结束，
           // 减少一些不必要的递归，同时也提前结束一些无用的递归
           if (sum > n || tempResult.size() > k) {
               return;
           }
           //循环条件就是从当前节点到集合的末尾
           //为什么从当前节点，不从1开始尼
           //一个原因就是为了去重，另一个原因就是自己和自己不能出现在同一个集合中
           for (int i = index; i <= 9; i++) {
               //回溯前的操作，
               //进入集合，并且记录集合中的值的和
               sum += i;
               tempResult.add(i);
               //递归本层下其余的集合
               trackBack(k, n, i + 1, tempResult, sum);
               //递归回溯到本层的时候，要移除之前对本层的操作，这样不影响本层其他节点的递归
               sum = sum - i;
               tempResult.remove(tempResult.size() - 1);
           }
       }
   ```

回溯---组合总和

摘要

您还没有登录,登录后即可评论

评论