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

leetcode 39. 组合总和 思考分析

这篇文章主要介绍了leetcode 39. 组合总和 思考分析的讲解,通过具体代码实例进行19281 讲解,并且分析了leetcode 39. 组合总和 思考分析的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=19281

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

目录

    • 1、题目
    • 2、思考分析
    • 3、未经优化代码
    • 4、剪枝优化

1、题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
leetcode 39. 组合总和 思考分析
leetcode 39. 组合总和 思考分析

2、思考分析

解空间树宽度部分即数组 candidates内集合,深度取决于target.
一开始的重复元素理解错误了,每层循环都从0开始:
for(int i=0;i<=candidates.size();i++)
这样是不对的,会产生重复组合。
我们仍然需要采用startindex作为for起始位置,不过对于下一层我们的startindex不是startindex+1,而是仍然是startindex,这样才能重复取相同元素。

leetcode 39. 组合总和 思考分析图1 for从0开始
leetcode 39. 组合总和 思考分析图2 for从i开始

3、未经优化代码

class Solution { public:     vector<vector<int>> result;     vector<int> res;     int sum;     void clear_solution_param()     {         result.clear();         res.clear();         sum=0;     }     void backtracking(vector<int>& candidates,int startindex,int n)     {            if(sum > n) return;         if(sum == n)         {             result.push_back(res);             return;         }         for(int i=startindex;i<candidates.size();i++)         {             //处理结点;             res.push_back(candidates[i]);             sum+=candidates[i];             //递归,探索下一层             backtracking(candidates,i,n);		//递归             sum-=candidates[i];             //回溯,撤销处理结果             res.pop_back();         }     }     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {         clear_solution_param();         backtracking(candidates,0,target);         return result;     } }; 

4、剪枝优化

先对数组进行排序,这样集合元素排列就是有序的了,方便剪枝。(这个在回溯法中经常用到)
对于同一层的for循环,如果sum加上此时的候选元素的和大于target则没有必要继续深入下去了。

class Solution { public:     vector<vector<int>> result;     vector<int> res;     int sum;     void clear_solution_param()     {         result.clear();         res.clear();         sum=0;     }     void backtracking(vector<int>& candidates,int startindex,int n)     {            if(sum > n) return;         if(sum == n)         {             result.push_back(res);             return;         }         for(int i=startindex;i<candidates.size();i++)         {             //由于输入的数组是有序的,所以直接进行剪枝。如果sum加上这个集合元素大于目标,此层就不需要往后看了,因为后面的元素加上sum肯定大于目标             if(sum+candidates[i]>n) break;             //处理结点;             res.push_back(candidates[i]);             sum+=candidates[i];             //递归,探索下一层             backtracking(candidates,i,n);		//递归             sum-=candidates[i];             //回溯,撤销处理结果             res.pop_back();         }     }     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {         clear_solution_param();         //排序加速剪枝         sort(candidates.begin(),candidates.end());         backtracking(candidates,0,target);         return result;     } }; 

本文转自互联网,侵权联系删除leetcode 39. 组合总和 思考分析

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

评论 抢沙发

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

b2b链

联系我们联系我们