区块链技术博客
www.b2bchain.cn

dfs求组合总和

这篇文章主要介绍了dfs求组合总和,通过具体代码讲解8093并且分析了dfs求组合总和的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了dfs求组合总和。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8093.html。具体如下:

39. 组合总和

 class Solution {     int len=0;     public List<List<Integer>> combinationSum(int[] candidates, int target) {        List<List<Integer>> ans=new ArrayList<>();        //DFS模拟一个栈        LinkedList<Integer> path=new LinkedList<>();              len=candidates.length;         // 先将数组排序,这一步很关键         // 排序是为了提前终止搜索         Arrays.sort(candidates);        if(candidates==null||len==0) return ans;         dfs(candidates,target,0,path,ans);        return ans;     }     private void dfs(int[] candidates,int target,int begin,LinkedList<Integer> path,List<List<Integer>> ans){       //结束条件。        if(target==0){            ans.add(new ArrayList<>(path));            return;        }         for(int i=begin;i<len;i++){            if(candidates[i]>target) break;             path.addFirst(candidates[i]);              // 可以重复,传递下去的是 i             dfs(candidates,target-candidates[i],i,path,ans);             path.removeFirst();        }             } }

40. 组合总和 II

 class Solution {     int len=0;     public List<List<Integer>> combinationSum2(int[] candidates, int target) {        List<List<Integer>> ans=new ArrayList<>();        //DFS模拟一个栈        LinkedList<Integer> path=new LinkedList<>();              len=candidates.length;         // 先将数组排序,这一步很关键         // 排序是为了提前终止搜索         Arrays.sort(candidates);        if(candidates==null||len==0) return ans;         dfs(candidates,target,0,path,ans);        return ans;     }     private void dfs(int[] candidates,int target,int begin,LinkedList<Integer> path,List<List<Integer>> ans){       //结束条件。        if(target==0){            ans.add(new ArrayList<>(path));            return;        }         for(int i=begin;i<len;i++){            if(candidates[i]>target) break;             //【修改1】 小剪枝             if (i > begin && candidates[i] == candidates[i - 1]) {                 continue;             }              path.addFirst(candidates[i]);              //【修改2】  不可以重复,传递下去的是 i+1             dfs(candidates,target-candidates[i],i+1,path,ans);             path.removeFirst();        }             } }

 

本文地址https://www.b2bchain.cn/8093.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » dfs求组合总和
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们