理解递归canSum函数
理解递归canSum函数
提问于 2021-01-05 20:27:29
我有一个函数，给定一个数字和一个数字列表，返回这个数字是否可以由列表中的数字组成，其中数字可以根据需要使用任意多次：
def canSum(target_sum, numbers, memo = {}):
if target_sum in memo:
return memo[target_sum]
if target_sum == 0:
return True
if target_sum < 0:
return False
for n in numbers:
remainder = target_sum - n
if canSum(remainder, numbers) == True:
memo[target_sum] = True
return True, memo
memo[target_sum] = False
return False,memo它应该返回True和False，这取决于target_sum是否可以通过在numbers列表中添加任意数量的时间来生成。
例如，canSum(4, [2])应该返回True，因为2+2是4，依此类推。然而，我不明白我的错误在哪里，下面所有的代码都应该返回True。
canSum(4,[2])
# (False, {2: True, 4: False})
canSum(4,[2,1])
# (False, {2: True, 1: True, 3: True, 4: False})
canSum(4,[1,2])
# (True, {1: True, 2: True, 3: True, 4: True})
canSum(10,[2])
# (False, {2: True, 4: False, 6: False, 8: False, 10: False})
canSum(10,[2,3])
# (False, {2: True, 1: False, 4: False, 3: True, 6: False, 5: True, 8: False, 7: True, 10: False})另外，是否有区别或需要将memo传递给递归函数调用？这似乎没有什么不同。
if canSum(remainder, numbers) == True: # -> if canSum(remainder, numbers, memo) == True:
memo[target_sum] = True
return True, memo回答 1
Stack Overflow用户
回答已采纳
发布于 2021-01-05 20:57:32
考虑一下，当你调用canSum(0, [2])时，函数将是返回文字True。且满足if canSum(0, [2]) == True条件。但是当您调用canSum(2, [2])时，函数将返回一个(True, {2: True})元组，而if canSum(2, [2]) == True条件将不会得到满足。因此，当您调用canSum(4, [2])时，该函数将返回(False, {2: True, 4: False})。
每次调用都必须以相同的格式返回。我认为这将是工作。
def canSum(target_sum, numbers, memo={}):
if target_sum in memo:
return memo[target_sum], memo
if target_sum == 0:
return True, memo
if target_sum < 0:
return False, memo
for n in numbers:
remainder = target_sum - n
if canSum(remainder, numbers)[0]:
memo[target_sum] = True
return True, memo
memo[target_sum] = False
return False, memo页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65578932
复制相关文章
相似问题
腾讯云开发者
