一天一大 lee(组合总和)难度:中等-Day20200909

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let _result = []
  function dfs(i, item, sum) {
    if (i >= candidates.length) return
    if (sum === target) {
      _result.push(item)
      return
    }
    dfs(i + 1, item, sum)
    if (target - sum - candidates[i] >= 0) {
      // 注意一个元素可以重复出现，则索引位不变
      dfs(i, [...item, candidates[i]], sum + candidates[i])
    }
  }

  dfs(0, [], 0)
  return _result
};