sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

组合总和-39 #72

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

给定一个无重复元素的数组  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]
]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这题乍一看很难,因为有重复元素,相对于之前的几道题来说引入了新的概念。

但是其实仔细想一下,之前的递归,我们对于 helper 递归函数每次递归都会把 start 起点 +1,如果我们每次递归不去 +1,而是把 start也考虑在内的话,是不是就可以把重复元素的情况也考虑进去了呢?

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
let combinationSum = function (candidates, target) {
  let res = []

  let helper = (start, prevSum, prevArr) => {
    // 由于全是正整数 所以一旦和大于目标值了 直接结束本次递归即可。
    if (prevSum > target) {
      return
    }
    // 目标值达成
    if (prevSum === target) {
      res.push(prevArr)
      return
    }

    for (let i = start; i < candidates.length; i++) {
      // 这里还是继续从start本身开始 因为多个重复值是允许的
      let cur = candidates[i]
      let sum = prevSum + cur
      let arr = prevArr.concat(cur)
      helper(i, sum, arr)
    }
  }

  helper(0, 0, [])

  return res
}
daomingQian commented 3 years ago
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
};