40. 组合总和 II

[buuing]

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

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

---

• 回溯算法

思路很简单, 首先通过从小到大排序数组, 然后通过prev剪掉小于上一层级的分支, 再通过set哈希表剪掉同一层级出现第二次的分支

const combinationSum2 = (candidates, target) => {
  candidates.sort((a, b) => a - b)
  const res = []
  const dfs = (map, arr, target, prev) => {
    if (target === 0) {
      return res.push(arr.slice())
    }
    const set = new Set()
    for (let i = 0; i < candidates.length; i++) {
      const curr = candidates[i]
      const next =  target - curr
      if (next < 0) break
      if (map[i] || prev > curr || set.has(curr)) continue
      set.add(curr)
      map[i] = 1
      arr.push(curr)
      dfs(map, arr, next, curr)
      map[i] = 0
      arr.pop()
    }
  }
  dfs([], [], target, 0)
  return res
}