问题描述:
给定一个无重复元素的数组 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; };
就是简单的依次招答案咯,再看大佬的解法:
妙在哪里呢:
第一先排序,当 target 小于集合中的某个元素时就终止遍历,优化了代码性能,第二 整个回溯过程,使用一个临时栈收集结果,每次遍历都将当前元素加入临时栈中,而后开始回溯,回溯过程中依次将符合条件的临时栈加入最终结果集,而在每次回溯结束,又将加入的元素进行出栈操作,为下一个元素的回溯做好了准备。
妙啊