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

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

注意：解集不能包含重复的组合。

思路

  1. 在 《组合总和》 递归逻辑的基础上，调整游标递增逻辑，而后将结果去重即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var combinationSum2 = function (candidates, target) {
  candidates = candidates.sort((a, b) => a - b)
  const result = []
  const marked = {}
  const searchTree = (startIndex, curVals, remainVal) => {
    if (remainVal === 0) {
      const key = curVals.join(',')
      if (!marked[key]) {
        result.push(curVals)
        marked[key] = true
      }
      return
    }
    if (startIndex >= candidates.length || remainVal < 0) {
      return
    }
    searchTree(startIndex + 1, [...curVals, candidates[startIndex]], remainVal - candidates[startIndex])
    searchTree(startIndex + 1, curVals, remainVal)
  }
  searchTree(0, [], target)
  return result
}

改良思路

  • 上述代码面对用例 candidates = [100 个 1], target = 30 时会超时，需要进行剪枝
  • 引入 sameCount 变量记录遍历数字的重复次数，递归时游标直接 +sameCount 处理 sameCount + 1 中情况即可
  • sameCount 带来的另一好处是输出结果唯一，无需去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var combinationSum2 = function (candidates, target) {
  candidates = candidates.sort((a, b) => a - b)
  const result = []
  const searchTree = (startIndex, curVals, remainVal) => {
    if (remainVal === 0) {
      result.push(curVals)
      return
    }
    if (startIndex >= candidates.length || remainVal < 0 || candidates[startIndex] > remainVal) {
      return
    }
    let sameCount = 1
    const keyVal = candidates[startIndex]
    while (startIndex + sameCount < candidates.length && candidates[startIndex + sameCount] === keyVal) {
      ++sameCount
    }
    const nextIndex = startIndex + sameCount
    for (let i = sameCount; i >= 0; --i) {
      searchTree(nextIndex, [...curVals, ...new Array(i).fill(keyVal)], remainVal - i * keyVal)
    }
  }
  searchTree(0, [], target)
  return result
}