40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8,
输出:
[
[1, 1, 6],
[1, 2, 5],
[1, 7],
[2, 6]
]

示例 2:
输入: candidates = [2, 5, 2, 1, 2], target = 5,
输出:
[
[1, 2, 2],
[5]
]

提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

来源：力扣（LeetCode）
链接：https:eetcode.cn/problems/combination-sum-ii

javascript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  candidates.sort((a, b) => a - b)
  const res = []
  dfs(candidates, target, 0, [], 0, res)
  return res
}

function dfs(candidates, target, start, combine, sum, res) {
  if (sum >= target) {
    if (sum == target) {
      res.push(combine.slice())
    }
    return
  }
  for (let i = start; i < candidates.length; i++) {
    if (i - 1 >= start && candidates[i - 1] == candidates[i]) {
      continue
    }
    combine.push(candidates[i])
    dfs(candidates, target, i + 1, combine, sum + candidates[i], res)
    combine.pop()
  }
}

console.log(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
console.log(combinationSum2([2, 5, 1, 3], 5))
console.log(combinationSum2([5, 2, 1, 2], 5))

40. 组合总和 II #

40. 组合总和 II