0040. 组合总和 II.md

40. 组合总和 II

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-jian-zhi-de-ling-yi-chong-si-lu-b-7ble/

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

  const result = []

  var search = (t, c, i) => {
    if (i === arr.length) {
      return
    }

    // 剪枝：同一层选择里，同一个数字只选择一次，所以一直找到下一个「和当前数字不相同的数字」为止
    let j = i
    while (arr[j] === arr[i]) {
      j++
    }
    search(t, c, j)

    const diff = t - arr[i]
    if (diff === 0) {
      result.push([...c, arr[i]])
    } else if (diff > 0) {
      search(diff, [...c, arr[i]], i + 1)
    }
  }

  search(target, [], 0)

  return result
};