40 组合总和 II

题目

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

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

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

示例 1:

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

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
  [1,2,2],
  [5]
]

提示:

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

思路

这一题很像三数之和的一般化。三数之和，可以通过双指针完成，但这里的一个有效解的长度是未知的，意味着并不能固定指针个数，而要动态增添指针。

第一眼的思路

我第一遍写，与前一道题相似，使用递归完成，基本思路是

1
2
3
combinationSum(candidates, target) = 
  combinationSum(candidates.slice(1), target) 
  + [candidates[0]] * combinationSum(candidates.slice(1), target - candidates[0])

在上述伪代码中，用 * 表示取两个二维数组的所有项的所有组合。如 [[1], [2]] * [[3]] = [[1,3], [2,3]]，特殊地，
[[1]] * [] = []，[[1]] * [[]] = [[1]]，这里，将 [] 看作这个运算的 0，将 [[]] 看作这个运算的单位1，可以帮助理解这个 * 运算符；

用 + 表示并集，此时 [] 为并集运算的单位1，任意数组与 [] 取并集仍然等于它自己。

则上述递归式表示对于给定的 candidates 和 target，组合总和就是以下两个解集的并集

  1. 不包括第一项的 candidates 和 target 的组合总和的解集
  2. 单独包括第一项的二维数组 * 不包括第一项的 candidates 和 target - 第一项 的组合总和的解集的运算结果

还是很晦涩……，以 candidates = [1,3] 和 target = 4 为例，简化方法名为 getCS：

1
2
3
4
5
6
7
8
9
getCS([1,3], 4)
= getCS([3], 4) + [[1]] * getCS([3], 3)
= getCS([], 4) + [[3]] * getCS([], 1) + [[1]] * getCS([3,4], 3)
= [] + [] + [[1]] * getCS([3,4], 3)
= [] + [] + [[1]] * (getCS([4], 3) + [[3]] * getCS([4], 0))
= [] + [] + [[1]] * (getCS([], 3) + [[4]] * getCS([], 3) + [[3]] * [[]])
= [] + [] + [[1]] * ([] + [] + [[4]] * [] + [[3]])
= [[1]] * [[3]]
= [[1,3]]

上述的伪代码里，getCS([4], 0) 表示从 [4] 这个数组中取个 0，很显然取不到，但是根据题意可以清楚，当算式简化为取 0 的时候，说明前面拆解的各项已经等于 target，此项的结果不应该否认前面算式的结果，所以应该假设 getCS(x, 0) = [[]]，这里的 x 可以是任意数组，只有这个式子等于 * 运算的单位1，才能保证不对前面的结果产生影响。

根据语意也可知，getCS([], y) 在 y ≠ 0 时，应该返回 []，表示无法组合，继而否定前面所有的 * 运算结果。

上述本是一个合理的运算过程，但是，这个算法过于 人类，对于组合数稍微增加的用例，其计算量会陡然增加，从而在运算时超时。极端的用例子是，[1,1,1,1,1,1,1...1] 共 40 个 1，计算对于 target = 30 的组合总和，肉眼看过去，解集中有且只有一个解，即取 30 个 1，但是代入上述的算法中，可以发现，算法算了无数次的 getCS([1,...,1], 30) 这类的值，毫无意义。所以不出意外地，这个算法超时了。

正解思路

之后我换用一种类似遍历树的思路，将一个值之后的其他所有值看作它的分叉，则将此题的 candidates 转换为了一个可以被广度遍历或者深度遍历的东西，当然，实际我并没有真的做这样的转换，因为没有必要。

具体做法是：

  1. 首先将 candidates 做升序排序，方便后面循环取值
  2. 设置一个解集 ans，存储遍历找到的解
  3. 接着设置一个当前遍历路径的数组 current 和 当前遍历路径的总和 sum
  4. 显然 current 和 sum 总是会一起变动，所以，可以写两个方法统一操作数组的值进出
  5. 接下来使用一个 head 指针，依次将 candidates 中的每一项看作是树的根节点，对每棵树做如下的循环操作
    1. 将当前节点加入遍历数组 current 中，将计算后的 sum 与 target 做判断
      • 若 sum 大于 target，则说明当前遍历数组不能满足题意，由于 candidates 是递增的，故当前项之后的所有项也不会满足题意，所以当前项的前一项也要替换为其下一项①
      • 若 sum 小于 target，则说明当前遍历路径可以继续，则对遍历指针进行递增操作即可。递增的后的指针有可能超出 candidates 的长度，此时需要将当前项与前一项一起删除，并取前一项的下一项继续遍历
      • 若两者相等，则将当前遍历路径增加到解集中。然后本应将当前项替换为下一项进行继续的遍历，但是仍然由于 candidates 是递增的，当前遍历数组如果恰好满足题意，则当前项之后的项替换当前项后的遍历数组，一定不满足题意，故直接删除当前项和前一项，取前一项的下一项继续遍历
    2. 当 head 指针超过 candidates 的长度后，循环结束
  6. 最后返回解集

①：这里的取下一项是指，遍历数组删除一项或多项后，取最后删除的元素在 candidates 中的下一个元素作为下一项。其中，与最后删除的元素值相等的元素应该直接跳过再取下一项，避免重复。因此，遍历数组 current 不仅存放元素，还有其对应的在 candidates 中的下标，即遍历数组 current 的大概格式为：

1
2
3
4
const current: Array<{
  value: number,
  index: number
}> = []

如果在遍历数组删除元素时，遍历数组清空，则意味着以当前 head 指针指向的元素作为树的有效路径被遍历完，则应该将 head 递增，这也是上述算法第 5 步可以跳出循环的原因。

例子

仍然以 candidates = [1,3] 和 target = 4 为例，

遍历的第一次循环，head 指向 1，遍历路径的和也为 1，递增遍历指针，然后 3 加入遍历数组。

此时的遍历数组为

1
2
3
4
5
6
7
8
9
10
current = [
  {
    value: 1,
    index: 0
  },
  {
    value: 3,
    index: 1
  }
]

遍历数组的和等于 target，解集增加解 [1,3]。

然后按算法，将当前项与前一项移除遍历数组，此时遍历数组清空，应取删除的最后一个元素 1 的下一项 3 重新加入遍历数组。

当然这次的循环是断然找不到解的，所以最后的解集为 [[1,3]]

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  // 排序数组，确保每一项都不大于后一项
  candidates.sort((a, b) => a - b);
  // 解集
  const ans = [];

  // 当前遍历路径，其中的 current 为遍历路径数组，sum 为遍历路径的和
  const road = {
    current: [],
    sum: 0,
  };

  // “树”根节点指针
  let head = 0;
  // 遍历指针
  let pt = 0;

  // 遍历路径增加一项
  const addItem = function (index) {
    const value = candidates[index];
    road.current.push({ value, index });
    // 由于 index 可能超出数组长度限制，所以设置默认加数为 0
    road.sum += value || 0;
  };

  // 按照 count 计数删除多项
  const popItems = function (count = 1) {
    let popped;
    for (let i = 0; i < count; i++) {
      popped = road.current.pop();
      road.sum -= popped.value || 0;
      if (!road.current.length) {
        const nextIndex = getNextIndex(popped.index, popped.value);
        head = nextIndex;
        return nextIndex;
      }
    }
    return getNextIndex(popped.index, popped.value);
  };

  // 根据当前位置和值取下一个不相等的值的索引
  const getNextIndex = function (index, value) {
    let nextIndex = index + 1;
    while (candidates[nextIndex] === value) nextIndex++;
    return nextIndex;
  };

  while (head < candidates.length) {
    addItem(pt);
    if (road.sum < target) {
      pt++;
      if (pt >= candidates.length) {
        pt = popItems(2);
      }
    } else if (road.sum === target) {
      ans.push(road.current.map((item) => item.value));
      pt = popItems(2);
    } else {
      pt = popItems(2);
    }
  }
  return ans;
};

这道题也挺有意思，虽然题意与上一道组合总和题相似，但是因为运算超时的原因，逼着我不得不使用非递归的方法实现