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 = 8
Output:
[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6]
]

Example 2:

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

Constraints:

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

analyze

是题目 39 的改版, 在 DFS 的基础上, 对于题目要求解集不能包含重复的组合要稍加处理。

思路: 递归解组合问题。

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])
  }
}