40. 组合总和 II

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

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

代码:

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //使用冒泡算法对数组排序(从大到小排序)
        int temp;
        for (int i = 0; i < candidates.length-1; i++) {
            for (int j = 0; j < candidates.length-i-1; j++) {
                if (candidates[j] < candidates[j + 1]) {
                    temp = candidates[j];
                    candidates[j] = candidates[j+1];
                    candidates[j+1] = temp;
                }
            }
        }
        return this.handle(candidates, target,0);
    }

    private List<List<Integer>> handle(int[] candidates, int target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = start; i < candidates.length; i++) {
            int c = candidates[i];
            if (i>start && candidates[i-1]==candidates[i]) {
                //避免重复组合
                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, i+1);
                for (List<Integer> list : lists) {
                    list.add(c);
                }
                res.addAll(lists);
            }
        }
        return res;
    }

}

本题是39. 组合总和这题的基础上进行修改得出,主要的变化是candidates数组中的数可以重复,且每个数字只能被使用1次。

我们考虑在39题的基础上进行改造,因为题目要求每个数字只能被使用1次,那么我们直接在handle函数上增加一个start参数,每一次递归调用的时候,都从下一个数开始找,这样就可以实现每个数字只会被使用1次。但是这也带来了1个问题,因为maxCandidate参数的存在,导致某些组合可能会丢失找不出来,而maxCandidate参数的作用是保证在每一次递归找结果的过程中,都只找比他小的数,也就是说,保证我们是从大数开始找。因为list的添加是从尾部添加的,所以得出最终组合结果都是从小到大排列。既然如此,我们何不直接在递归调用之前,先对数组candidates进行从大到小排序,这样既可去掉maxCandidate这个参数。相应的,我们的避免重复组合的判断方式也要进行相应的修改,只要这个数已经出现过查找过1次,就可以跳过。


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

番茄红素维生素E软胶囊增强免疫力喜倍力搭配片男性成人保健品 1瓶装60粒
¥46.00
卫龙魔芋爽600g香辣素毛肚休闲零食大礼包情人节送女友生日礼物辣条
¥35.90
墨斗鱼 大自然套装 香薰精油无火香薰精油补充液室内卫生间香薰炉灯卧室香水香氛复方植物精油
¥48.90
银华棠医用壳聚糖痔疮洗液痔疮膏孕妇肛门肉球瘙痒内外混合治痔除疮软膏的药肛裂便秘便血男女创面愈合凝胶
¥29.00
喜宝莉一次性加厚洗珍珠纹洗脸巾干湿两用抽取式60片加厚加大200*200mm
¥13.93
内廷上用灰甲灵冷敷凝胶足部肿胀疼痛灰指甲足痒足癣足臭甲癣
¥49.80
有质 400ml注水冰袋【30只装】加厚母乳保鲜户外食品海鲜冷藏冰包
¥17.90
五虎爪 婴儿口罩10枚3d立体婴童口罩宝宝一次性口罩新生幼儿透气防护专用0-6月到1岁半 款式随机 白色
¥26.80