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