博客列表 >分享一个妙极的算法

分享一个妙极的算法

子龙的博客搬家啦httpswwwcnblogscomZiLongZiLong
子龙的博客搬家啦httpswwwcnblogscomZiLongZiLong原创
2019年03月11日 20:27:14900浏览

问题描述:

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

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

说明:

所有数字(包括 target)都是正整数。

解集不能包含重复的组合。 

思路:

穷举,遍历candidates数组中的每一项,看看target-candidates 是否为0 有则加入结果集,无则遍历candidates 子集和target-candidates 的结果,这种解法科学上好像叫回溯backTrack,先贴一下自己的ac代码,作为引出大佬解法的一个引子吧:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    
    let ret = [];
    
    for( let i = 0 , L = candidates.length; i < L;i++){
        if( target- candidates[i] == 0 ){
            ret.push([candidates[i]])
        }else if( target- candidates[i] > 0 ){
            let temp = []  ;
            let curRet = combinationSum( candidates.slice(i),target- candidates[i] )
            
            if( curRet && curRet.length > 0 ){
                curRet.forEach(item => {
                    item.unshift(candidates[i])
                })
                ret.push(...curRet)
            }
        }
    }
    return ret;
};

就是简单的依次招答案咯,再看大佬的解法:

微信图片_20190311201655.png


妙在哪里呢:

第一先排序,当 target 小于集合中的某个元素时就终止遍历,优化了代码性能,第二 整个回溯过程,使用一个临时栈收集结果,每次遍历都将当前元素加入临时栈中,而后开始回溯,回溯过程中依次将符合条件的临时栈加入最终结果集,而在每次回溯结束,又将加入的元素进行出栈操作,为下一个元素的回溯做好了准备。

妙啊

声明:本文内容转载自脚本之家,由网友自发贡献,版权归原作者所有,如您发现涉嫌抄袭侵权,请联系admin@php.cn 核实处理。
全部评论
文明上网理性发言,请遵守新闻评论服务协议