组合总和-39

力扣（LeetCode） 链接：https://leetcode.cn/problems/combination-sum/

答案

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const res = []
  const path = []
  candidates.sort((a, b) => a - b)
  function bfs(start, sum) {
    if (sum === target) {
      res.push([...path])
      return
    }
    for (
      let i = start;
      i < candidates.length && target - sum >= candidates[start];
      i++
    ) {
      path.push(candidates[i])
      bfs(i, sum + candidates[i])
      path.pop()
    }
  }
  bfs(0, 0)
  return res
}

思考

如果不给 start 开始索引会怎么样？

会出现重复数据

var combinationSum = function (candidates, target) {
  const res = []
  const path = []
  candidates.sort((a, b) => a - b)
  function bfs(sum) {
    if (sum === target) {
      res.push([...path])
      return
    }
    for (
      let i = 0;
      i < candidates.length && target - sum >= candidates[i];
      i++
    ) {
      path.push(candidates[i])
      bfs(i, sum + candidates[i])
      path.pop()
    }
  }
  bfs(0)
  return res
}
combinationSum([2, 3, 6, 7], 7)
// 错误答案  [[2,2,3],[3,2,2],[7]]
// 正确答案  [[2,2,3],[7]]