LeetCode刷题Java版039.组合总和

作者：沉默王二
发布时间：2022-09-10T07:42:05.111+0800

---

039.组合总和

题意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制 重复 被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

难度

中等

示例

输入：candidates = [2,3,6,7], target = 7

解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

分析

从示例中可以看得出，这道题需要我们从整数数组中不断地排列组合，找出所有符合要求的答案。

可问题是，一个个找的时候，很容易重复枚举，导致大量的时间被浪费。虽然可以利用哈希表去记录排列组合的哈希值，但是，当数组非常大的时候，仍然很有可能枚举重复，有没有更好的办法呢？

有！

我们可以给数组candidates[]中的每一个元素编号，这样在枚举时，编号形成的序列，肯定要保持非严格的单调上升的顺序，也就是number[ans[i]] <= number[ans[i + 1]]（见后面的代码），为什么要有=呢？因为每个数字可以用多次，我们只要保证下一个用的不是之前用过的就可以了。

这样子就不会出现有枚举重复的情况了，注意一下递归枚举的结束条件——枚举的数总和大于等于target，以及不要忘记每次 状态回溯 的时候的处理，这时候就可以很快速的把这道题目过掉了。

class Solution {

    private void DFS(List nowSta,int tot,int begin,int target,int[] candidates){        if(tot == target){            ans.add(new ArrayList<>(nowSta));            return ;        }        for(int i = begin;i < candidates.length;i++){            if(tot + candidates[i] > target)                continue;            nowSta.add(candidates[i]);            DFS(nowSta,tot + candidates[i],i,target,candidates);            nowSta.remove(nowSta.size() - 1);//记得删除最后一个，不要忘记状态的回溯！！！        }    }    public List<List> combinationSum(int[] candidates, int target) {        Arrays.sort(candidates);        List inque = new ArrayList<>();        DFS(inque,0,0,target,candidates);        return ans;    }}

至于时间嘛，还可以。

这道题目的时间复杂度并不好分析，因为这个剪枝能够优化的地方非常多，难以用一个简洁的数学式子来描述，

但是复杂度的上界可以粗略的算出，是

因为每个数最多被用到次，而对于每个数我们又有选和不选两种情况，所以最多是上述的时间复杂度，但是因为我们利用了 按顺序枚举 这个方法，所以基本不可能跑到这个上界。

总结

本题还是基础的递归搜索，需要注意的是状态的回溯，这一类枚举的题目，最重要的地方就是状态的回溯，它决定了你之后搜索的对与错，同样这个点也是许多初学者容易遗忘的地方。

力扣链接：https://leetcode.cn/problems/combination-sum/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 770 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

039.组合总和

题意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制 重复 被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

难度

中等

示例

输入：candidates = [2,3,6,7], target = 7

解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

分析

从示例中可以看得出，这道题需要我们从整数数组中不断地排列组合，找出所有符合要求的答案。

可问题是，一个个找的时候，很容易重复枚举，导致大量的时间被浪费。虽然可以利用哈希表去记录排列组合的哈希值，但是，当数组非常大的时候，仍然很有可能枚举重复，有没有更好的办法呢？

有！

我们可以给数组candidates[]中的每一个元素编号，这样在枚举时，编号形成的序列，肯定要保持非严格的单调上升的顺序，也就是number[ans[i]] <= number[ans[i + 1]]（见后面的代码），为什么要有=呢？因为每个数字可以用多次，我们只要保证下一个用的不是之前用过的就可以了。

这样子就不会出现有枚举重复的情况了，注意一下递归枚举的结束条件——枚举的数总和大于等于target，以及不要忘记每次 状态回溯 的时候的处理，这时候就可以很快速的把这道题目过掉了。

class Solution {

    private void DFS(List nowSta,int tot,int begin,int target,int[] candidates){        if(tot == target){            ans.add(new ArrayList<>(nowSta));            return ;        }        for(int i = begin;i < candidates.length;i++){            if(tot + candidates[i] > target)                continue;            nowSta.add(candidates[i]);            DFS(nowSta,tot + candidates[i],i,target,candidates);            nowSta.remove(nowSta.size() - 1);//记得删除最后一个，不要忘记状态的回溯！！！        }    }    public List<List> combinationSum(int[] candidates, int target) {        Arrays.sort(candidates);        List inque = new ArrayList<>();        DFS(inque,0,0,target,candidates);        return ans;    }}

至于时间嘛，还可以。

这道题目的时间复杂度并不好分析，因为这个剪枝能够优化的地方非常多，难以用一个简洁的数学式子来描述，

但是复杂度的上界可以粗略的算出，是

因为每个数最多被用到次，而对于每个数我们又有选和不选两种情况，所以最多是上述的时间复杂度，但是因为我们利用了 按顺序枚举 这个方法，所以基本不可能跑到这个上界。

总结

本题还是基础的递归搜索，需要注意的是状态的回溯，这一类枚举的题目，最重要的地方就是状态的回溯，它决定了你之后搜索的对与错，同样这个点也是许多初学者容易遗忘的地方。

力扣链接：https://leetcode.cn/problems/combination-sum/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 770 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

039.组合总和

题意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制 重复 被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

难度

中等

示例

输入：candidates = [2,3,6,7], target = 7

解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

分析

从示例中可以看得出，这道题需要我们从整数数组中不断地排列组合，找出所有符合要求的答案。

可问题是，一个个找的时候，很容易重复枚举，导致大量的时间被浪费。虽然可以利用哈希表去记录排列组合的哈希值，但是，当数组非常大的时候，仍然很有可能枚举重复，有没有更好的办法呢？

有！

我们可以给数组candidates[]中的每一个元素编号，这样在枚举时，编号形成的序列，肯定要保持非严格的单调上升的顺序，也就是number[ans[i]] <= number[ans[i + 1]]（见后面的代码），为什么要有=呢？因为每个数字可以用多次，我们只要保证下一个用的不是之前用过的就可以了。

这样子就不会出现有枚举重复的情况了，注意一下递归枚举的结束条件——枚举的数总和大于等于target，以及不要忘记每次 状态回溯 的时候的处理，这时候就可以很快速的把这道题目过掉了。

class Solution {

    private void DFS(List nowSta,int tot,int begin,int target,int[] candidates){        if(tot == target){            ans.add(new ArrayList<>(nowSta));            return ;        }        for(int i = begin;i < candidates.length;i++){            if(tot + candidates[i] > target)                continue;            nowSta.add(candidates[i]);            DFS(nowSta,tot + candidates[i],i,target,candidates);            nowSta.remove(nowSta.size() - 1);//记得删除最后一个，不要忘记状态的回溯！！！        }    }    public List<List> combinationSum(int[] candidates, int target) {        Arrays.sort(candidates);        List inque = new ArrayList<>();        DFS(inque,0,0,target,candidates);        return ans;    }}

至于时间嘛，还可以。

这道题目的时间复杂度并不好分析，因为这个剪枝能够优化的地方非常多，难以用一个简洁的数学式子来描述，

但是复杂度的上界可以粗略的算出，是

因为每个数最多被用到次，而对于每个数我们又有选和不选两种情况，所以最多是上述的时间复杂度，但是因为我们利用了 按顺序枚举 这个方法，所以基本不可能跑到这个上界。

总结

本题还是基础的递归搜索，需要注意的是状态的回溯，这一类枚举的题目，最重要的地方就是状态的回溯，它决定了你之后搜索的对与错，同样这个点也是许多初学者容易遗忘的地方。

力扣链接：https://leetcode.cn/problems/combination-sum/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 770 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412