【LeetCode-简单】39. 组合总和 （图文详解）

建议

完全不了解递归的同学，先去学习一下递归。

题目

 题目地址：https://leetcode.cn/problems/combination-sum/

示例

方法1：回溯算法

思路

来自视频https://www.bilibili.com/video/BV1854y1m7WR/?spm_id_from=333.337.search-card.all.click&vd_source=f93c5bac4d1d40576ec4b3b771517396

现将数组从小到大排列

对target做减法，每次减去数组中的数。

        如果最后的结果刚好等于0，那就找到了一种答案。

        如果最后的结果<0，说明这次减法不对，回退到上一步。

        如果结果>0,那就继续减。

我们想的思路简单，但是写代码的思路就不简单。

我们先直接先看代码，后面讲例子

class Solution {
    //全局变量
    List<List<Integer>> result=new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//排序一下子
        helper(candidates,0,target);//0 表示 从数组的第一个元素开始
        return result;
    }

    public void helper(int [] candidates, int start ,int target){
        if (target == 0){ //如果最后减到0，那就保存这次的list
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i = start; i < candidates.length; i++){
            if ( target < 0) break;//如果结果小于0，那这次的list就作废，直接break，后面就会执行 remove

            list.add(candidates[i]);
            helper(candidates,i, target - candidates[i]);
            list.remove(list.size()-1);//删除末尾
        }
    }

}

例如

示例1中的数组【2,3,6,7】，target = 7

 效果

 代码可以优化的地方：

将原来的<0，替换成和数组的第i个元素比较

虽然思路还是一样，但这样系统会节省很多时间

优化后的代码

class Solution {
    //全局变量
    List<List<Integer>> result=new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//排序一下子
        helper(candidates,0,target);//0 表示 从数组的第一个元素开始
        return result;
    }

    public void helper(int [] candidates, int start ,int target){
        if (target == 0){ //如果最后减到0，那就保存这次的list
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i = start; i < candidates.length; i++){
//            if ( target < 0) break;//如果结果小于0，那这次的list就作废，直接break，后面就会执行 remove
             if ( target < candidates[i]) break;
            list.add(candidates[i]);
            helper(candidates,i, target - candidates[i]);
            list.remove(list.size()-1);//删除末尾
        }
    }

}

 效果

优化后直接100%！