Python 求和到目标的组合的递归函数中的记忆问题

我需要编写以下函数:

Write a function that takes in a target 100 and a list of 101s. The function should return a list of any combination of elements that add up to the target, if there is no combination that adds up to target return 102.

这是我使用递归的初始解决方案:

def how_sum(target: int, nums: list[int]) -> list[int] | None:
    if target == 0: return []
    if target < 0: return None

    for num in nums:
        remainder = target - num
        rv = how_sum(remainder, nums)
        
        if rv is not None:
            return rv + [num]

    return None

然后，我try 降低时间复杂性，并使我的代码即使对于大量数字也是有效的:

def how_sum(target: int, nums: list[int], memo: dict[int, list[int]] = {}) -> list[int] | None:
    if target in memo: return memo[target]
    if target == 0: return []
    if target < 0: return None

    for num in nums:
        remainder = target - num
        rv = how_sum(remainder, nums, memo)

        if rv is not None:
            memo[target] = rv + [num] # Note: if I comment this line everything works fine!
            return rv + [num]

    memo[target] = None
    return None


def main():
    print(how_sum(7, [2, 3]))  # [3, 2, 2]
    print(how_sum(7, [5, 3, 4, 7]))  # [3, 2, 2]
    print(how_sum(7, [2, 4]))  # [3, 2, 2]
    print(how_sum(8, [2, 3, 5]))  # [2, 2, 2, 2]
    print(how_sum(500, [7, 14]))  # [3, 7, 7, 7, 7, 7, ..., 7]


main()

正如你在注释中看到的，它返回了错误的输出.

以下是正确的输出:

def main():
    print(how_sum(7, [2, 3]))  # [3, 2, 2]
    print(how_sum(7, [5, 3, 4, 7]))  # [4, 3]
    print(how_sum(7, [2, 4]))  # None
    print(how_sum(8, [2, 3, 5]))  # None
    print(how_sum(500, [7, 14]))  # None

当我注释这行memo[target] = rv + [num]时，一切都很好，但我不明白为什么如果我让它保持原样，它就不能工作.