递归与回溯6：LeetCode39组合总和（可重复使用）

递归与回溯6：LeetCode39组合总和（可重复使用）

LeetCode39和40题都是组合总和的问题，唯一的区别是元素是否可以重复使用。39题是可以重复的，而40题是不可以的。我们来看一下。

LeetCode39题目要求：

给你一个 无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

例子：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

这个题虽然说数字可以重复，那如果是0怎么办呢？题目在提示部分说了，1 <= candidates[i] <= 200，所以最坏的情况都全都取1，则有target个1。因此因为有总和的限制，因此并不是无限重复的。

我们先不想回不回溯的问题，就看该怎么做，比如所对于序列{2,5,3},target=7。很显然我们可以先选择一个2，然后剩下的就是7-2=5。之后再选一个2，剩余5-2=3。之后再选一个2，剩余3-2=1。已经小于2了，所以我们不能继续向下了，要返回一下。看看有没有3。OK，序列中有3，那么就得到了第一个结果{2,2,3}。

之后我们继续回退到只选了一个2的时候，找找看有没有5。OK，有的，所以得到了第二个结果{2,5}。

一次类推，当我们不考虑2，只从后面的5和3中无法得到结果，所以我们最终得到的结果就是{2,2,3}和{2,5}。就是这么简单！

接着，我们将上面的过程画成一个树形图：

这个图仍然是纵向在递归，横向是针对每个元素的暴力枚举，从左到右选过的就不再选重复选了。 

这里的target其实增加了我们的判断条件和回溯 *** 作。注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的 限制，只要选取的元素总和超过target，就返回!

所以实现代码也不复杂：

class Solution {
    List> res = new ArrayList<>(); //记录答案
    List path = new ArrayList<>();  //记录路径

    public List> combinationSum(int[] candidates, int target) {
        dfs(candidates,0, target);
        return res;
    }
    public void dfs(int[] c, int u, int target) {
        if(target < 0) return ;
        if(target == 0)
        {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = u; i < c.length; i++){
            if( c[i] <= target)  
            {
                path.add(c[i]);
                dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是i
                path.remove(path.size()-1); //回溯，恢复现场
            }
        }
    }
}

上面的代码看起来比较简洁，但是在java里一般不提倡定义全局变量，而且这里是局部方法修改全局变量，会让java工程师非常不爽，所以我们还是将其改造成参数的形式。当然代价是代码看起来略显得复杂，其实和上面的完全一样。

public List> combinationSum(int[] candidates, int target) {
        List> res = new ArrayList<>(); //记录答案
        List path = new ArrayList<>();  //记录路径
        dfs(candidates,0, target,res,path);
        return res;
    }
    public void dfs(int[] c, int u, int target,List> res, List path) {
        if(target < 0) return ;
        if(target == 0)
        {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = u; i < c.length; i++){
            if( c[i] <= target)  
            {
                path.add(c[i]);
                dfs(c,i,target -  c[i],res,path); // 因为可以重复使用，所以还是i
                path.remove(path.size()-1); //回溯，恢复现场
            }
        }
    }