您的位置:首页 > 游戏 > 手游 > 深圳住房和城乡建设局官网_重庆做网站重庆做网站_站长工具樱花_seo推广价格

深圳住房和城乡建设局官网_重庆做网站重庆做网站_站长工具樱花_seo推广价格

2024/12/5 21:30:05 来源:https://blog.csdn.net/weixin_73939095/article/details/143737503  浏览:    关键词:深圳住房和城乡建设局官网_重庆做网站重庆做网站_站长工具樱花_seo推广价格
深圳住房和城乡建设局官网_重庆做网站重庆做网站_站长工具樱花_seo推广价格

仅为个人记录复盘学习历程,解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

39. 组合总和

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

提供参数:int数组candidates,目标数值target。

主要操作:

递归三要素

1.返回值类型和输入参数:
遍历整棵解空间树,使用全局变量res作为结果集,使用全局变量path记录单条结果,返回值类型为void,需要输入candidates数组作为参数,还有目标值target,起始位置startIndex(避免额外操作),累加和sum。

2.终止条件:

2.1sum与目标值target相同,将结果记录到结果集中,返回。

2.2sum大于目标值target,直接返回。

3.单层递归逻辑:

从起始索引位置startIndex遍历数组candidates,在遍历时递归向下探索解空间树,同时返回时进行回溯。

代码大致如下:

    public List<List<Integer>>res=new ArrayList<>();public List<Integer>path=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {//由于for循环条件判断时使用了剪枝,这里需要排序,否则会缺失部分结果。Arrays.sort(candidates);backTrace(candidates,target,0,0);return res;}   public void backTrace(int[]candidates,int target,int sum,int startIndex){//终止条件if(sum==target){res.add(new ArrayList(path));return;}//单层递归逻辑//sum+candidates[i]<=target此处进行剪枝。for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);backTrace(candidates,target,sum,i);path.remove(path.size()-1);sum-=candidates[i];}}

自己尝试解题的代码(虽然能通过但是很乱):

    public List<List<Integer>>res=new ArrayList<>();public List<Integer>path=new ArrayList<>();public int value;public List<List<Integer>> combinationSum(int[] candidates, int target) {backTrace(candidates,target);return res;}   public void backTrace(int[]candidates,int target){//终止条件if(value==target){List<Integer>temp2=new ArrayList(path);Collections.sort(temp2);for(int i=0;i<res.size();i++){List<Integer>temp1=new ArrayList(res.get(i));Collections.sort(temp1);if(temp1.equals(temp2)){return;}}res.add(new ArrayList(path));return;}//单层递归逻辑for(int i=0;i<candidates.length&&(value<=target);i++){path.add(candidates[i]);value+=candidates[i];backTrace(candidates,target);value-=candidates[i];path.remove(path.size()-1);}}

这个问题感觉和背包问题有些相似之处,但不完全等同。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com