0

我有一个函数，给定一个数字和一个数字列表，如果该数字可以由列表中的数字组成，则返回该函数，其中数字可以根据需要多次使用：

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
4

1 回答 1

1

考虑当您调用时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
于 2021-01-05T12:57:31.577 回答