中山建网站报价,wordpress换回原版编辑器,竞价网站单页,邢台做wap网站找谁难度
中等
题目
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意#xff1a;解集不能包含重复的组合。
示例 1:
输入: candidat…难度
中等
题目
给定一个候选人编号的集合 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
2class 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])# 集合中 每各元素只能添加一次所以添加完当前的元素后去下一层试探的时候只能从下一位开始遍历所以下一层的开始位置就是i1self.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)
