原题，下面是题目描述：
我称之为两数之和plus plus版，一个数字可以重复使用，最近都在做这种递归的题目，这题其实也比较显然的递归。我们遍历列表，找到一个小于当前target的数字就进入下一次递归（大于就直接进入下一次循环了，等于更不必说，直接加入我们的结果数组中），每次加入数字时将当前数字减去。但是这样会有很多的重复项，比如题目中的例子：
[2,3,6,7],target=7。 如果我们直接将数组传入下一个递归中，那么很显然，遍历到2时会得到2，2，3这个序列，但是当我们遍历到3时，又会得到3，2，2这个序列，题目中并没说顺序不一样也行，那显然这个是一个重复序列，需要去掉。
那如何去掉？还是上面的例子，我们遍历到 2 的时候，放入下一次递归，我们一定能够遍历到后面的 3 ，所以我们其实已经将 2，2，3 这个序列加入到结果数组里了，在遍历到 3 时根本无需考虑前面的数字。OK，思路就有了，我们直接传递一个开始下标到下一次递归，让其不要遍历之前的数字即可，这样就去掉了重复值。
代码一
我们写下第一版代码：
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
ArrayList<List<Integer>> combinationSumRes = new ArrayList<>();
int len = candidates.length;
for (int i = 0; i < len; i++) {
ArrayList<Integer> list = new ArrayList<>();
if (candidates[i] == target) {
list.add(candidates[i]);
combinationSumRes.add(list);
continue;
}
if (candidates[i] > target) {
continue;
}
int[] t = new int[len - i];
System.arraycopy(candidates, i, t, 0, len - i);
list.add(candidates[i]);
ArrayList<List<Integer>> lists = combinationSum2(t, target - candidates[i], list);
combinationSumRes.addAll(lists);
}
return combinationSumRes;
}
public ArrayList<List<Integer>> combinationSum2(int[] candidates, int target, List<Integer> l) {
if (target < 0) {
return new ArrayList<>();
}
int len = candidates.length;
ArrayList<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < len; i++) {
ArrayList<Integer> list = new ArrayList<>(l);
if (candidates[i] > target) {
continue;
}
if (candidates[i] == target) {
list.add(candidates[i]);
res.add(list);
continue;
}
int[] t = new int[len - i];
System.arraycopy(candidates, i, t, 0, len - i);
list.add(candidates[i]);
ArrayList<List<Integer>> lists = combinationSum2(t, target - candidates[i], list);
res.addAll(lists);
}
return res;
}
}
代码和前面的思路非常吻合，提交后一次通过，但是速度并不理想，那我们需要接着优化。在这种递归和循环的代码中，最耗时的代码往往是创建对象。我们递归里创建了两个对象，一个是res结果数组，一个是list，路径上的数字的数组。list数组是无法优化掉的，因为题目需要我们提供具体的数字，所以必须要将路径记录下来。那res可以优化吗？显然可以，这里 res 数组在递归中作用很简单，将吻合的路径加入，然后返回给调用。我们其实可以直接设置一个类变量，符合要求直接加入其中即可，这样还可以省掉返回值。
代码二
我们就有了优化后的代码：
class Solution {
ArrayList<List<Integer>> combinationSumRes = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
for (int i = 0; i < len; i++) {
ArrayList<Integer> list = new ArrayList<>();
if (candidates[i] == target) {
list.add(candidates[i]);
combinationSumRes.add(list);
continue;
}
if (candidates[i] > target) {
continue;
}
list.add(candidates[i]);
combinationSum2(candidates,i, target - candidates[i], list);
}
return combinationSumRes;
}
public void combinationSum2(int[] candidates, int start, int target, List<Integer> l) {
if (target < 0) {
return;
}
int len = candidates.length;
for (int i = start; i < len; i++) {
if (candidates[i] > target) {
continue;
}
ArrayList<Integer> list = new ArrayList<>(l);
if (candidates[i] == target) {
list.add(candidates[i]);
combinationSumRes.add(list);
continue;
}
list.add(candidates[i]);
combinationSum2(candidates,i, target - candidates[i], list);
}
}
}
优化后的代码提交一次过，速度大幅提升，打败百分之99。我们可以试着分析一下时间复杂度。这里情况有点复杂，我们分析最差时间复杂度，我们最差情况，会递归数组长度，我们设为 n ，每个递归内最差循环数组长度。
那这里最差时间复杂度应该为 O( n! )。