题目分析

题目给出的算法结构为：

首先题目要求返回的类型为 List<List<Integer>> ， 那么我们就新建一个 List<List<Integer>> 作为全局变量 ， 最后将其返回 。

再看看返回的结构 ， List<List<Integer>> 。 因此我们需要写一个包含 List<Integer> 的辅助函数 ， 加上一些判断条件 ， 此时结构变成了

重点就是如何进行递归 。 递归的第一步 ， 当然是写递归的终止条件啦 ， 没有终止条件的递归会进入死循环 。 那么有 哪些终止条件呢？由于条件中说了都是正整数 。 因此 ， 如果 target<0当然是要终止了 ， 如果 target==0 ， 说明此时找到了一组数的和为 target ， 将其加进去 。 此时代码结构变成了这样 。

我们是要求组成 target 的组合 。 因此需要一个循环来进行遍历 。 每遍历一次 ， 将此数加入 list ， 然后进行下一轮递归 。 代码结构如下 。

似乎初具规模 ， 测试一把结果如下

结果差距有点大 ， 为何会出现如此大的反差 。 而且发现一个规律 ， 后面的一个组合会包含前面一个组合的所有的数字 ， 而且这些数加起来和 target 也不相等啊 。 原因出在哪呢？java 中除了几个基本类型 ， 其他的类型可以算作引用传递 。 这就是导致 list 数字一直变多的原因 。 因此 ， 在每次递归完成 ， 我们要进行一次回溯 。 把最新加的那个数删除 。 此时代码结构变成这样 。

再测一下 ， 结果如下：

还是不对 。 这次加起来都等于 7 了 ， 和上次结果相比算是一个很大的进步了 。 分析下测试结果 。 不难能看出 ， 本次结果的主要问题包含了重复的组合 。 为什么会有重复的组合呢？因为每次递归我们都是从 0 开始 ， 所有数字都遍历一遍 。 所以会出现重复的组合 。 改进一下 ， 只需加一个 start 变量即可 。 talk is cheap show me the code 。

代码如下：

最后再测一下 。

代码通过 ， 但是效率并不高 。 本题有效果更好的动态规划的解法 。 本文主要展示递归回溯 ， 就不做具体介绍了 。

是不是有点感觉了 ， 那么再来一题 。

力扣 77. 组合（点击查看题目）

题目描述

给定两个整数 n 和 k ， 返回 1 ... n 中所有可能的 k 个数的组合 。

示例:

题目给出的算法结构为

按照前面的套路 ， 首先建一个 ArrayList<List<Integer>> res 作为全局变量 。 顺带建一个含有 List<Integer>list 的辅助函数 。

此时结构变成如下所示 。

对于辅助递归函数 。 第一步当然是列出终止条件 ， 避免进入死循环 。 由于题目要求是所有 k 个数的组合 。 那么很容易知道递归的终止条件为 list.size() == k 。

因此 ， 代码结构可变为如下所示 。

接下来要进入重头戏了 ， 递归回溯的整个过程 。 整个递归过程不就是一直将数字加入 list 么 。 因此可以用一个循环 。

在循环中主要做三件事

1.加此轮的数据加入 list 。

2.递归进行下一步调用 。

3.删除此轮加入的数据进行回溯 。

此时代码结构如下：

代码大致结构以及形成 ， 测试一下 ， 结果如下 。