### 40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8Output:[  [1,1,6],  [1,2,5],  [1,7],  [2,6]]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5Output:[  [1,2,2],  [5]]

Constraints:

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

### analyze

1. 对 candidates 排序。
2. 对这种情况要过滤: i !== start && candidates[i] === candidates[i - 1], 可以以 ([1, 1, 2], 3) 这个例子进行思考不产生两个 [1, 2]。

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum2 = function (candidates, target) {  const result = []
const sortCandidates = candidates.sort((r1, r2) => r1 - r2)  const DFS = function (sum, arr, start) {    if (sum === target) {      result.push(arr.slice())      return    }    if (sum > target) {      return    }
for (let i = start; i < sortCandidates.length; i++) {      if (i !== start && sortCandidates[i] === sortCandidates[i - 1]) { // [1,1,2], 3。避免产生两个 [1, 2]        continue      }
sum += sortCandidates[i]      arr.push(sortCandidates[i])      DFS(sum, arr, i + 1)      arr.pop(sortCandidates[i])      sum -= sortCandidates[i]    }  }
DFS(0, [], 0)
return result};

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */var combinationSum2 = function (candidates, target) {  const result = []  const sorted = candidates.sort((r1, r2) => r1 - r2)  recurcive(sorted, target, 0, [], result)  return result};
var recurcive = function (candidates, target, start, temp, result) {  if (target < 0) {    return  }
if (target === 0) {    result.push([...temp])    return  }
for (let i = start; i < candidates.length; i++) {    if (candidates[i] === candidates[i - 1] && i !== start) {      continue    }    temp.push(candidates[i])    target = target - candidates[i]    recurcive(candidates, target, i + 1, temp, result)    target = target + candidates[i]    temp.pop(candidates[i])  }}