【leetcode39】【DFS模板】组会求和

最新推荐文章于 2024-05-29 17:05:10 发布

原创最新推荐文章于 2024-05-29 17:05:10 发布 · 185 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#leetcode #dfs

leetcode 同时被 2 个专栏收录

132 篇文章

订阅专栏

Java-pat

113 篇文章

订阅专栏

本文深入探讨了LeetCode上组合总和问题的解决方案，详细解释了如何通过深度优先搜索(DFS)策略找到所有可能的组合，使数组元素之和等于目标数。文章提供了两种优化的DFS实现方式，包括减少重复计算和引入剪枝操作，以提高算法效率。

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1.下面是写dfs的基本模板–参考来自b站 https://www.bilibili.com/video/av94518806

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] p, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        dfs(p,target,new ArrayList<>(),res);

        return res;
    }

    //1.定义一个dfs函数  参数列表定义
    void dfs(int[] p,int target,List<Integer> chain,List<List<Integer>> res){
        //2.截止条件
        int sum = getSum(chain);
        if(sum>=target){
            if(sum==target){
                //8.组合 需要去重
                List<Integer> tmp = new ArrayList<>(chain);//3.引用类型 最好重新拷贝一份
                Collections.sort(tmp);
                if(!res.contains(tmp)){
                    res.add(tmp);
                } 
            }
            return;
        }


        //4.候选结点的条件--数组中每个结点都可以作为候选结点
        for(int i=0;i<p.length;i++){
            int c = p[i];//5.这里的c是每一个候选结点
            //6.回溯--标记--删除标记
            chain.add(c);
            //7.判断是否需要筛选---这里每个候选结点都是可以重复使用的，所以不需要筛选条件--所有的候选结点都可以进入下一层dfs
            dfs(p,target,chain,res);

            chain.remove(chain.size()-1);
        }

    }
     int getSum(List<Integer> chain){
            int res = 0;
            for(int i:chain){
                res+=i;
            }
            return res;
        }

}

但是上面的代码需要多次计算getSum，复杂度高，可以使用target相减的方式。
在这里插入图片描述

class Solution {
    public List<List<Integer>> combinationSum(int[] p, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Arrays.sort(p);
        dfs(p,target,new ArrayList<>(),res);

        return res;
    }

    //1.定义一个dfs函数  参数列表定义
    void dfs(int[] p,int target,List<Integer> chain,List<List<Integer>> res){
        //2.截止条件
        
        if(target==0){
             
                //8.组合 需要去重
                List<Integer> tmp = new ArrayList<>(chain);//3.引用类型 最好重新拷贝一份
                Collections.sort(tmp);
                if(!res.contains(tmp)){
                    res.add(tmp);
                } 
            
            return;
        }


        //4.候选结点的条件--数组中每个结点都可以作为候选结点---这里添加了剪枝操作
        for(int i=0;i<p.length;i++){
            int c = p[i];//5.这里的c是每一个候选结点
            if(target-p[i]<0){
                break;
            }

            //6.回溯--标记--删除标记
            chain.add(c);
            //7.判断是否需要筛选---这里每个候选结点都是可以重复使用的，所以不需要筛选条件--所有的候选结点都可以进入下一层dfs
            dfs(p,target-p[i],chain,res);

            chain.remove(chain.size()-1);
        }

    }
    

}