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参数结合代码中红色部分,那么我们可以控制组合结果一定是按照从小到大排列的,从而实现了去重效果,还去掉了多余的递归操作。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

维特丝(vetes)泡沫发蜡喷雾干胶定型弹力素羊毛卷男女保湿蓬松发胶 泡沫发蜡450ml+旅行装99ml
¥34.00
维特丝(vetes)一梳黑染发剂染发梳植物潮色显白遮盖白发自然清水纯黑发焗油男女梳炫彩 自然黑LW00
¥49.00
维特丝(vetes)染发笔遮白补染快速染发天然植物一次性染发棒 一次性染发棒黑色
¥46.00
维特丝 护发精油防毛躁清香玫瑰奇焕亮发干枯烫发卷发直发头发润发护发素男女士 滋养柔顺护发精油100ml
¥36.00