每天一道算法题：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

思路

和 39 题类似但是不能有重复的解，使用回溯试探法，但是过程要考虑去重。
数组中可能出现重复的数字，但是结果中不能出现重复的解，在处理过程中就要进行去重和剪枝。首先对 candidates 数组进行排序，在递归的过程中，当发现当前元素与前一个元素相同，并且前一个元素已经被考虑过（不在当前组合中），就跳过当前元素。
从数组的第一个元素开始，依次考虑是否选择该元素，再递归地考虑下一个元素，每个数字只能使用一次，因此在递归调用时，下一轮搜索的起始位置应该是当前位置的下一个位置。

代码

"""
10,1,2,7,6,1,5
8如果不排序的情况(10) > 8
1 2 7 > 8
1 2 6 > 8
1 2 1 5 > 8
1 2 5 = 81 7   = 8
1 6 1 = 8
1 1 5 遍历完成
1 5   遍历完成2 7   > 8
2 6   = 8
2 1 5 = 8 重复了 去重的方法 就是将所有的子集排序后，再进行去重，这样是再将所有的接过遍历完成之后，才能去重，效率非常低
2 52 7 > 8
2 6 = 8
2"""class Solution:def combinationSum2(self, candidates, target):self.candidates = candidates# 先对所有元素进行排序，再递归过程中进行去重，如果相邻的两个值相同，并且前一个值已经选过了，就不会选self.candidates.sort()self.target = targetself.length = len(self.candidates)self.cache = []self.result = []self.backtrack(0, [], self.target)print(self.result)return self.resultdef backtrack(self, start, tmp, target):# start 在当前层遍历的开始位置# tmp 记录临时值的栈# target 目标值，当目标值为0是 就可以终止递归# 当目标值为0的时候就终止递归，记录此时的组合if target == 0:self.result.append(tmp[:])returnfor i in range(start, self.length):# 在同一层遍历的时候，如果两个相邻的元素相同，就跳过 使用i-1就说明 上一个位置的值已经被选过了# i > start 因为要和前一个元素比较，所以i的值必须时大于start的，不然会越界if i > start and self.candidates[i] == self.candidates[i - 1]:continue# 如果当前值比目标值小 或者 相等的时候，才去递归下一层，不然直接跳过if target >= self.candidates[i]:tmp.append(self.candidates[i])# 集合中 每各元素只能添加一次，所以添加完当前的元素后，去下一层试探的时候只能从下一位开始遍历，所以下一层的开始位置就是i+1self.backtrack(i + 1, tmp, target - self.candidates[i])tmp.pop()if __name__ == '__main__':candidates = [10, 1, 2, 7, 6, 1, 5]target = 8# candidates = [2, 5, 2, 1, 2]# target = 5s = Solution()s.combinationSum2(candidates, target)