给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意： 解集不能包含重复的组合。
示例 1:

  1. 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  2. 输出:
  3. [
  4. [1,1,6],
  5. [1,2,5],
  6. [1,7],
  7. [2,6]
  8. ]

示例 2:

  1. 输入: candidates = [2,5,2,1,2], target = 5,
  2. 输出:
  3. [
  4. [1,2,2],
  5. [5]
  6. ]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50

  • 1 <= target <= 30

    解法一：回溯

    1. function combinationSum2(candidates: number[], target: number): number[][] {
    2. let res: Array<Array<number>> = []
    3. candidates.sort((a, b) => a -b)
    4. let n = candidates.length
    5. let used = Array(n).fill(false)
    7. function recursion(total: number, path: Array<number>, idx: number) {
    8.   if (total > target) {
    9.     return
    10.   }
    11.   if (total === target) {
    12.     res.push([...path])
    13.     return
    14.   }
    16.   for (let i = idx; i < n; i++) {
    17.     const tmp = candidates[i]
    18.     if (total + tmp > target) {
    19.       break
    20.     }
    21.     if (i > 0 && tmp === candidates[i-1] && !used[i-1]) {
    22.       continue
    23.     }
    24.     total += tmp
    25.     path.push(tmp)
    26.     used[i] = true
    27.     recursion(total, path, i + 1)
    28.     path.pop()
    29.     total -= tmp
    30.     used[i] = false
    31.   }
    33. }
    34. recursion(0, [], 0)
    35. return res
    36. };