[Leetcode][python]Combination Sum/组合总和
[Leetcode][python]Combination Sum/组合总和
蛮三刀酱
发布于 2019-03-26 16:24:35
发布于 2019-03-26 16:24:35
题目大意
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
解题思路
回溯，答案代码是从小到大，我一开始的思路是从大到小，然后就递归次数过多…..
代码
从小到大，将candidates的数字逐步加入，一旦超过target就将candidates切片后再加
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not candidates:
return []
candidates.sort()
result = []
self.combination(candidates, target, [], result)
return result
def combination(self, candidates, target, current, result):
# print candidates
if current:
# print current
s = sum(current)
else:
s = 0
if s > target:
return 1
if s == target:
result.append(current)
return 1
if s < target:
for i, v in enumerate(candidates):
flag = self.combination(candidates[i:], target, current + [v], result)
if flag == 1:
break总结
这是我已开始写的，最后报错是：
Line 15: RuntimeError: maximum recursion depth exceeded在数据集：
[92,71,89,74,102,91,70,119,86,116,114,106,80,81,115,99,117,93,76,77,111,110,75,104,95,112,94,73]
310说明前面的数据集对了，我觉得写的应该没问题了，应该是递归次数过多的问题，有空看下。
class Solution(object):
result_list = []
def combine(self, i, temp, target, candidates):
# print 'start:', temp
if i >= 0:
temp.append(candidates[i])
print temp, 'this:', candidates[i], 'sum:', sum(temp)
if sum(temp) == target:
self.result_list.append(temp)
return self.combine(candidates.index(temp[0])-1, [], target, candidates)
elif sum(temp) > target:
temp.pop()
return self.combine(i-1, temp, target, candidates)
else:
return self.combine(i, temp, target, candidates)
else:
# print(temp)
if temp == []:
return
cut = candidates.index(temp[-1]) - 1
# print 'daodi', cut
temp.pop()
return self.combine(cut, temp, target, candidates)
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
i = len(candidates) - 1
candidates.sort()
self.combine(i, [], target, candidates)
return self.result_list本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年09月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录