39. 组合总和

>> 饿了么、美团外卖红包领取地址<<

题目：https://leetcode-cn.com/problems/combination-sum/submissions/

代码：

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return this.handle(candidates, target, target);
    }

    private List<List<Integer>> handle(int[] candidates, int target, int maxCandidate) {
        List<List<Integer>> res = new ArrayList<>();
        for (int c : candidates) {
            if (c > maxCandidate) {
                //避免重复组合
                continue;
            }
            if (c == target) {
                //刚好相等，这个数直接是结果
                List<Integer> list = new ArrayList<>();
                list.add(c);
                res.add(list);
            } else if (c < target) {
                //小于，递归
                List<List<Integer>> lists = this.handle(candidates, target - c, c);
                for (List<Integer> list : lists) {
                    list.add(c);
                }
                res.addAll(lists);
            }
        }
        return res;
    }

}

题目的意思其实就是把target这个数分解成candidates数组中的数，使用递归的做法即可实现，具体实现可以参考代码。

一个需要注意的点是为什么我递归的函数要增加一个maxCandidate的参数，这个参数主要的作用是用来组合去重。参考如下这么一个例子：

candidates=[2,3,6,7]，target=7。

没有使用maxCandidate参数去重的话，得出结果为：[[3, 2, 2], [2, 3, 2], [2, 2, 3], [7]]。可以看到存在重复的组合，如果我们增加了maxCandidate参数结合代码中红色部分，那么我们可以控制组合结果一定是按照从小到大排列的，从而实现了去重效果，还去掉了多余的递归操作。