LeetCode40-组合总数II
自己果然还是一个3分钟热血的人儿啊
曾憧憬着每天会刷一道LeetCode
到了现在
才发现,热情已逐渐消退
虽然最近是有些忙
但感觉还是没有了以前的热情
得找回之前的初心啊!
40-组合总数II
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
思路:
这一题和上一题十分相似,我刚开始还以为会简单些,因为考虑的情况变少了。也就是给定数组candidates里的元素不能任意拿取了,组合的元素必须是数组里已有的,不能随意重复。但细细想想才发现难度其实是有所增加了。因为本题与上题有一个最大的不同就是给定的candidates列表里面元素是可以重复的,这里面的重复是给定的candidates列表里可能有重复数字,而上一题中的candidates列表里没有重复数字,所以如何去重就是本题的关键了。核心思路也是采用回溯法。
程小新同学:LeetCode--回溯法心得zhuanlan.zhihu.com
我的思想如下:
- 先采用回溯法找出 candidates 中所有可以使数字和为 target 的组合,这里面可以有重复的组合。
- 最后在给获得组合去重,这个去重方法其实算是傻瓜式方法,但自己确实是找不到更好的去重方法了,要是哪位笔友有更好的方法,请不吝赐教啊!!!
代码如下:
class Solution:
# 本题和39题一样,均是采用回溯法,刚开始感觉本题比上题还要简单,因为考虑的情况变少了
# 但其实是难度有所增加了,因为本题与上题有一个最大的不同就是给定的candidates列表里面元素是可以重复的
# 所以如何去重就是本题的关键了
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]-->指代给定的数字列表
:type target: int-->指代给定的最终目标值
:rtype: List[List[int]]-->指代最终要返回的结果列表
"""
# 首先将给定的candidates列表从小到大排序,此步也是第一步去重操作
candidates.sort()
# 定义保存最终结果的列表
final_result = []
# 核心的递归函数
def back(answer=[], start=0, target=target):
"""
:param answer: List[int]-->指代临时存储的结果列表
:param start: Int-->指代每次递归操作遍历candidates列表的起始值
:param target: int-->指代每次递归操作后所要判断的目标值
:return: None
"""
# 如果临时目标值为0,说明已经得到了一个答案。但是此答案是否为我们所需的不重复的答案,得再次判断
if target == 0:
# 此for循环为final_result结果集查重操作,一旦发现得到的新answer与final_result里面的结果相同,立即舍弃
for index in final_result:
if index == answer:
return
final_result.append(answer)
return
for index in range(start, len(candidates)):
# 如果当前列表中的值不大于临时目标值,说明可以继续递归循环查找答案了;反之则立即退出当前循环
if candidates[index] <= target:
new_target = target-candidates[index]
# new_answer = []
# new_answer.extend(answer)
# new_answer.append(candidates[index])
# 这一步start必须是得重新赋值,否则会有重复值
start += 1
back(answer+[candidates[index]], start, new_target)
else:
break
back()
return final_result
if __name__ == "__main__":
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
result = Solution().combinationSum2(candidates, target)
print(result)
执行效率还算是不错的,在80%以上。