递归函数中用于查找求和到目标的组合的记忆问题

Question

我需要编写以下函数：

编写一个接受目标

(int)

和

int

列表的函数。该函数应返回加起来达到目标的任意元素组合的列表，如果没有加起来达到目标的组合，则返回

None

。

这是我使用递归的初步解决方案：

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

然后我尝试降低时间复杂度并使我的代码即使对于大量数据也能高效：

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]

一切正常，但我不明白为什么如果我保持原样它就不起作用。

Answer 1

我发现这段代码有两个问题。首先您关于此输入的正确解决方案的主张：

print(how_sum(8, [2, 3, 5]))  # None

似乎不正确。鉴于解释，

[3, 5]

或

[2, 2, 2, 2]

都是有效答案。同样适用于：

 print(how_sum(7, [5, 3, 4, 7]))  # [4, 3]

其中

[7]

也是有效结果。就您的代码问题而言，该问题是一个常见问题，因为您在没有保证的情况下使用了危险的默认值：

def how_sum(target, nums, memo={})

由于顶级调用之间的

nums

不同，因此必须在每次递归开始时重新初始化

memo

缓存。否则，您会得到上次运行的结果，其中

nums

不同。一种可能的方法：

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

    if target not in memo:
        memo[target] = None

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

                if rv is not None:
                    memo[target] = [*rv, num]
                    break

    return memo[target]