发布于2019-11-17 16:59 阅读(872) 评论(0) 点赞(14) 收藏(4)
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为: [ [1,2,2], [5] ]
利用回溯法子集树模板,注意这里的判断要大量用到求和,所以利用模板中的01映射
会花费大量的时间,这里不用01映射,再加个全局的和变量记录,降低每次求和带来的时间消耗
。
事实上模板用的01映射只是帮助理解问题,理解后皆可取消模板内的01映射。
class Solution:
def __init__(self):
self.data = []
self.n = 0
self.tempRes = []
self.res = []
self.target = 0
self.sumNum = 0
def backtrack(self, k):
if k>=self.n or self.sumNum >= self.target:
if self.sumNum == self.target:
self.res.append(self.tempRes[:])
else:
for i in [0, 1]:
if i==1:
data = self.data[k]
self.tempRes.append(data)
self.sumNum += data
self.backtrack(k+1)
if i==1:
self.tempRes.pop()
self.sumNum -= data
def combinationSum2(self, candidates, target):
self.data = sorted(candidates)
self.n = len(candidates)
self.target = target
self.backtrack(0)
res = list(map(list,set(map(tuple, self.res))))
return res
作者:放羊人
链接:https://www.pythonheidong.com/blog/article/158332/920840c5f9522c2e8cc4/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!