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

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

如果文章对您有帮助的话,欢迎老板打赏↑↑↑(请我吃饭😋