LeetCode 40. 组合总和 II（中）

如何去掉一个数组中重复的元素，除了使用哈希表以外，我们还可以先对数组升序排序，重复的元素一定不是排好序以后的第 1 个元素和相同元素的第 1 个元素。根据这个思想，我们先对数组升序排序是有必要的。候选数组有序，对于在递归树中发现重复分支，进而“剪枝”也是有效的。

题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 

示例

示例 1: 

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2: 
1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

考察知识点

数组、回溯算法、hash表

核心思想

方法一、加法回溯加重复判断

主要难点有两个：1、一个数字本身不能重复用。2、去掉重复的组合。

如何去掉一个数组中重复的元素，除了使用哈希表以外，我们还可以先对数组升序排序，重复的元素一定不是排好序以后的第 1 个元素和相同元素的第 1 个元素。根据这个思想，我们先对数组升序排序是有必要的。候选数组有序，对于在递归树中发现重复分支，进而“剪枝”也是有效的。所以，这道题和39题非常像，先排序，再剪枝，但是由于禁止每一个数字出现多次，只能出现一次，所以，在剪枝后面，再加一个重复数字判断就行。

1
2
3
# 在这里进行一个判断，过滤掉那些一样的数字。
if index > begin and candidates[index - 1] == candidates[index]: 
	continue
4.png

为何说“黄色框住部分的 2'' 与前一个分支的 2' 在数值上相等，而前一个分支（也就是 2' ）考虑的数组范围更大”？这是因为2'在输入的candidates [1, 2', 2'', 2''', 5] 中处于最靠前面，其后面的数字，在接下来的子节点都会被考虑到，而 2'' 在 2' 的后面，所以2'' 考虑的范围一定会小一点，肯定会和前面出现重复，所以黄色框部分要去掉。

大佬题解

方法二

除了用if语句判断以外，还可以用hash表记录出现次数，来防止重复。

待完成

Python版本

方法一的实现

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
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(candidates, begin, path, res, length):
            if sum(path) == target:
                res.append(path[:])
                return
            for index in range(begin, length):
                if (sum(path) + candidates[index]) > target:  # 剪枝判断，如果当前位置的数字大于residue，由于是sort了的，那后面也不用看了，接break掉。
                    break
                if index > begin and candidates[index-1] == candidates[index]:  # 在这里进行一个判断，过滤掉那些紧随其后一样的数字，这么写就是为了防止不同数字重复解的出现。
                    continue
                path.append(candidates[index])
                backtrack(candidates, index+1, path, res, length)  # 注意，在上面判断之后，这里传入到下一个backtrack的begin也变成了index+1，这么写就是为了防止数字本身重复。
                path.pop()

        length = len(candidates)
        if length == 0:
            return []
        
        candidates.sort()
        path = []
        res = []
        backtrack(candidates, 0, path, res, length)
        return res

print("leet code accept!!!")
Input = [[10,1,2,7,6,1,5], [2,5,2,1,2]]
Input1 = [8, 5]
Answer = [
    [
        [1, 7],
        [1, 2, 5],
        [2, 6],
        [1, 1, 6]
    ],
    [
        [1,2,2],
        [5]
    ]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.combinationSum2(Input[i], Input1[i])
        print(reslut)
        print(Answer[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        candidates.sort()
        n = len(candidates)
        res = []
        
        def backtrack(i, tmp_sum, tmp_list):
            if tmp_sum == target:
                res.append(tmp_list)
                return 
            for j in range(i, n):
                if tmp_sum + candidates[j]  > target : break
                if j > i and candidates[j] == candidates[j-1]:continue
                backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])
        backtrack(0, 0, [])    
        return res