题目:
难度:Middle
相关话题:数组
、回溯算法
给定一个无重复元素 的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
所有数字(包括 target
)都是正整数。
解集不能包含重复的组合。
示例1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
思路:
回溯
,每一次回溯,遍历当前数组尝试每一个值。
由于要求不包含重复组合,不使用hash
的话,就对每一次回溯都只遍历上一次遍历最后的索引i
之后的值;
但题目提示每个值都能重复使用无限次,因此每次遍历都从上一个i
开始,既可以保证没有重复的组合,也确保每个值都尽可能的多用。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
let result=[]
backtrack([],target,0)
return result
function backtrack(temp,rest,start){
if(rest<0)return
if(rest===0)result.push(temp.slice())
for(let i=start;i<candidates.length;i++){
temp.push(candidates[i])
backtrack(temp,rest-candidates[i],i)
temp.pop()
}
}
};