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次,就可以跳过。


支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏