You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
var combinationSum = function(candidates, target) {
let res = []
let len = candidates.length
function sum(arr) {
return arr.reduce((pre, cur) => pre + cur, 0)
}
function tfs(start, path) {
if (sum(path) === target) {
res.push([...path])
return
}
if (sum(path) > target) {
return
}
for (let i = start; i < len; i++) {
path.push(candidates[i])
tfs(i, path)
path.pop()
}
}
tfs(0, [])
return res
};
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这题乍一看很难,因为有重复元素,相对于之前的几道题来说引入了新的概念。
但是其实仔细想一下,之前的递归,我们对于
helper
递归函数每次递归都会把start
起点 +1,如果我们每次递归不去 +1,而是把start
也考虑在内的话,是不是就可以把重复元素的情况也考虑进去了呢?The text was updated successfully, but these errors were encountered: