题目:

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

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

说明：

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

示例:

1. 示例 1

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

1. 示例 2

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

抛砖引玉

抛砖引玉

思路

本题逻辑的重点在不允许 candidates 的元素重复使用，但是 candidates 元素本身可能存在重复元素

• candidates 中同一个元素不能在一种组合中重复使用
• 结果元素相同组成的子元素位置不同算作一种结果

day-08: 组合 (难度:中等)

day-09: 组合总和 (难度:中等)

在前两天的题目中分别用：

1. 指针驱动选择生成组合
2. 指针约束区域枚举指定区域元素来枚举组合

两种形式处理了递归回溯子元素组合的问题

结合本题的要求：

• 指针可以协助完成同一个元素不能在一种组合中重复使用
• 如果采用指针驱动的形式，发现很难避免不同位置的元素形成相同元素的结果，而采用约束区域来枚举元素的形状，相同的元素（对 candidates 排序，相邻元素相同）被指针约束则很好避免在不同个组合中信息相同个元素

实现

• 对 candidates 排序(将相同元素排列在一起，方便指针控制元素不重复参与组合)
• 递归，从i之后遍历为参与组合元素:
• 在i指针之后遇到相同元素，则不再选择i处元素，因为此时已回溯，再次选择i处元素则形成了重复的组合

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  let _result = []
  candidates = candidates.sort((a, b) => a - b)
  function dfs(i, item, sum) {
    if (sum === target) {
      _result.push(item)
      return
    }
    for (let x = i; x < candidates.length; x++) {
      if (target - sum - candidates[x] >= 0) {
        // i指针所在元素如果后面还有与其相同的元素，则不再选择i处元素，因为此时已回溯，再次选择i处元素则形成了重复的组合
        if (x != i && candidates[x] == candidates[x - 1]) continue
        item.push(candidates[x])
        dfs(x + 1, [...item], sum + candidates[x])
        item.pop()
      }
    }
  }
  dfs(0, [], 0)
  return _result
}