Leetcode 40. 组合总和 II

1.题目描述

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

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

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

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

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

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

2.思路分析

本题与Leetcode 39 组合总和的区别:

• 本题candidates 中的每个数字在每个组合中只能使用一次。
• 本题数组candidates的元素是有重复的，而Leetcode 39 组合总和是无重复元素的数组candidates

本题涉及到去重:顾名思义就是 使用过的元素不能重复选取

举一个例子，candidates = [1, 1, 2], target = 3， candidates已经排序了

回溯三部曲：

• 确定回溯函数的参数以及返回值

  # 存放结果集
  result = []
  # 存放符合条件的结果(叶子结点的结果)
  path = []
  def backtracking(candidates: List[int], target: int, path_sum: int, start_index: int) -> None:
  1
  2
  3
  4
  5

• 确定终止条件

  从上图的树形结构中可以看出:sum>=target时,递归终止,sum==target时收集结果

     # Base Case
          if path_sum == target:
              self.paths.append(path[:]) # 因为shallow copy，不能直接传入path
              return
          if path_sum > target:
              return 
  1
  2
  3
  4
  5
  6

• 确定单层搜索逻辑

  • 如果判断同一树层上元素（相同的元素）是否使用过 ?

• 如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

      # 单层递归逻辑
        for i in range(start_index, len(candidates)):
            # 剪枝，
            if path_sum + candidates[i] > target:
                return
            
            # 检查同一树层是否出现曾经使用过的相同元素
            # 若数组中前后元素值相同，但前者却未被使用(used == False)，说明是for loop中的同一树层的相同元素情况
            if i > 0 and candidates[i] == candidates[i-1] and self.usage_list[i-1] == False:
                continue

            path_sum += candidates[i]
            self.path.append(candidates[i])
            self.usage_list[i] = True
            self.backtracking(candidates, target, sum_, i+1)
            self.usage_list[i] = False  # 回溯，为了下一轮for loop
            self.path.pop()             # 回溯，为了下一轮for loop
            path_sum -= candidates[i]       # 回溯，为了下一轮for loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.代码实现

# 回溯+used数组
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 有重复元素 去重的问题
        # 定义全局变量
        result, path = [], []
        use_list = [False] * len(candidates)

        # 回溯函数要处理的参数以及返回值
        def backtrack(candidates: List[int], target: int, path_sum: int, startIndex: int) -> None:
            # 终止条件
            if path_sum > target:
                return
            if path_sum == target:
                result.append(path[:])
                return
            # 单层循环逻辑
            for i in range(startIndex, len(candidates)):
                # 剪枝
                if path_sum + candidates[i] > target:
                    return
                # 去重 检查同一层中是否存在重复元素
                if i > 0 and candidates[i] == candidates[i - 1] and use_list[i - 1] == False:
                    continue
                # 处理节点
                path.append(candidates[i])
                path_sum += candidates[i]
                use_list[i] = True
                # 递归
                backtrack(candidates, target, path_sum, i + 1)
                # 回溯
                use_list[i] = False
                path.pop()
                path_sum -= candidates[i]

        # 预先排序
        candidates.sort()
        backtrack(candidates, target, 0, 0)
        return result
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

# 回溯
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 有重复元素 去重的问题
        # 定义全局变量
        result, path = [], []


        # 回溯函数要处理的参数以及返回值
        def backtrack(candidates: List[int], target: int, path_sum: int, startIndex: int) -> None:
            # 终止条件
            if path_sum > target:
                return
            if path_sum == target:
                result.append(path[:])
                return
            # 单层循环逻辑
            for i in range(startIndex, len(candidates)):
                # 剪枝
                if path_sum + candidates[i] > target:
                    return
                # 去重 检查同一层中是否存在重复元素
                if i > startIndex and candidates[i] == candidates[i - 1] :
                    continue
                # 处理节点
                path.append(candidates[i])
                path_sum += candidates[i]

                # 递归
                backtrack(candidates, target, path_sum, i + 1)
                # 回溯

                path.pop()
                path_sum -= candidates[i]

        # 预先排序
        candidates.sort()
        backtrack(candidates, target, 0, 0)
        return result
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