python中的递归没有达到正确的结果

Question

我有一个问题，想要找到列表子集的总和为特定值的方式数。但是，如果我手动运行递归公式，我会得到一个与 python 代码不同的（正确的）值。我错过了什么，或者为什么我得到不同的结果？

假设我有一个列表b = [2,3,2,1,4]，目标值为T = 5. 然后将有 4 个子集与目标值相加：

{b[0], b[1]}

{b[0], b[2], b[3]}

{b[4], b[3]}

{b[1], b[2]}

以下代码给出的结果为 2，但我希望它返回 4。

b = [2,3,2,1,4]

def subset_sum(T, idx):

    if T < 0 or idx< 0:

        return 0

    if T == 0:

        return 1

    else:

        return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1) 

if __name__ == "__main__":

    print(subset_sum(5, 4))

基于@TomDalton 评论进行编辑：我尝试了这个并认为这可能是因为两个 if 语句没有同时检查 - 因此在 idx = 0 并且我们从值 T 中减去 b[0] 的情况下，然后在下一次迭代中它将返回 0，因为它在检查 T == 0 之前检查 idx < 0。虽然我不确定我的猜测的有效性

Answer 1

这是带有额外检测的代码，可帮助跟踪输出，缩进递归调用。您会注意到计数的一个严重问题：当您获得所需的总数并到达列表末尾时，您返回0而不是1。这会阻止您通过使用最终列表元素正确累积获得正确总数的解决方案，因为在检查是否获得正确总数之前，您会重复超过列表末尾。维修在底部。indent = ""b = [2,3,2,1,4]def subset_sum(total, idx):&nbsp; &nbsp; global indent&nbsp; &nbsp; print(indent + "ENTER", total, idx)&nbsp; &nbsp; indent += "&nbsp; "&nbsp; &nbsp; if total < 0 or idx < 0:&nbsp; &nbsp; &nbsp; &nbsp; result = 0&nbsp; &nbsp; elif total == 0:&nbsp; &nbsp; &nbsp; &nbsp; result = 1&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; result = subset_sum(total, idx-1) + subset_sum(total-b[idx], idx-1)&nbsp;&nbsp; &nbsp; indent = indent[2:]&nbsp; &nbsp; print(indent + "LEAVE", total, idx, result)&nbsp; &nbsp; return resultif __name__ == "__main__":&nbsp; &nbsp; print(subset_sum(5, 4))输出：ENTER 5 4&nbsp; ENTER 5 3&nbsp; &nbsp; ENTER 5 2&nbsp; &nbsp; &nbsp; ENTER 5 1&nbsp; &nbsp; &nbsp; &nbsp; ENTER 5 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 5 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 5 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 3 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 3 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 5 0 0&nbsp; &nbsp; &nbsp; &nbsp; ENTER 2 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 2 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 2 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 0 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 0 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 2 0 0&nbsp; &nbsp; &nbsp; LEAVE 5 1 0&nbsp; &nbsp; &nbsp; ENTER 3 1&nbsp; &nbsp; &nbsp; &nbsp; ENTER 3 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 3 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 3 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 1 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 1 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 3 0 0&nbsp; &nbsp; &nbsp; &nbsp; ENTER 0 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 0 0 1&nbsp; &nbsp; &nbsp; LEAVE 3 1 1&nbsp; &nbsp; LEAVE 5 2 1&nbsp; &nbsp; ENTER 4 2&nbsp; &nbsp; &nbsp; ENTER 4 1&nbsp; &nbsp; &nbsp; &nbsp; ENTER 4 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 4 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 4 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 2 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 2 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 4 0 0&nbsp; &nbsp; &nbsp; &nbsp; ENTER 1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 1 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 1 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER -1 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE -1 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 1 0 0&nbsp; &nbsp; &nbsp; LEAVE 4 1 0&nbsp; &nbsp; &nbsp; ENTER 2 1&nbsp; &nbsp; &nbsp; &nbsp; ENTER 2 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 2 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 2 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 0 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 0 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 2 0 0&nbsp; &nbsp; &nbsp; &nbsp; ENTER -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE -1 0 0&nbsp; &nbsp; &nbsp; LEAVE 2 1 0&nbsp; &nbsp; LEAVE 4 2 0&nbsp; LEAVE 5 3 1&nbsp; ENTER 1 3&nbsp; &nbsp; ENTER 1 2&nbsp; &nbsp; &nbsp; ENTER 1 1&nbsp; &nbsp; &nbsp; &nbsp; ENTER 1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER 1 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE 1 -1 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ENTER -1 -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LEAVE -1 -1 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE 1 0 0&nbsp; &nbsp; &nbsp; &nbsp; ENTER -2 0&nbsp; &nbsp; &nbsp; &nbsp; LEAVE -2 0 0&nbsp; &nbsp; &nbsp; LEAVE 1 1 0&nbsp; &nbsp; &nbsp; ENTER -1 1&nbsp; &nbsp; &nbsp; LEAVE -1 1 0&nbsp; &nbsp; LEAVE 1 2 0&nbsp; &nbsp; ENTER 0 2&nbsp; &nbsp; LEAVE 0 2 1&nbsp; LEAVE 1 3 1LEAVE 5 4 22修理在检查是否超出列表末尾之前，只需检查是否成功：if total == 0:&nbsp; &nbsp; result = 1elif total < 0 or idx < 0:&nbsp; &nbsp; result = 0

Answer 2

您是否考虑过迭代方法？itertools.combinations想到itertools.combinations(iterable, r)从输入可迭代返回 r 个长度的元素子序列。组合按字典排序顺序发出。因此，如果输入可迭代对象已排序，则组合元组将按排序顺序生成。有了这个，您可以执行以下操作：from itertools import combinationsdef count_subsets(main_list, target):&nbsp; &nbsp; result = 0&nbsp; &nbsp; for i in range(len(main_list)):&nbsp; &nbsp; &nbsp; &nbsp; sets = combinations(main_list, i)&nbsp; &nbsp; &nbsp; &nbsp; result += sum(sum(subset) == target for subset in sets)&nbsp; &nbsp; return result

Answer 3

问题是你在 idx < 0 时退出，但没有先检查是否 T == 0（这将是一个解决方案）。您应该首先测试 T == 0：if T == 0:&nbsp; &nbsp; return 1elif T < 0 or idx< 0:&nbsp; &nbsp; return 0else:&nbsp; &nbsp; return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1)&nbsp;