我想计算数组A = [2, 1, 1, 4]的子集的个数，其和为2.有两种方式:(A[0])和(A[1], A[2]).我的计算代码是:
def W(number, index):
A = [2, 1, 1, 4]
if number < 0 or index < 0:
return 0
elif number==0:
return 1
else:
return W(number, index-1) + W(number - A[index], index)
现在，当我用W(2,3)调用函数时，得到的是4，而不是2.我的问题是，我的代码还计算了可能性(A[1], A[1])和(A[2], A[2]).在仍然使用递归的情况下，有没有办法修复它？
拨打W(number - A[index], index)应该是W(number - A[index], index - 1)；否则，允许重复计算子集和中的一个元素.
下面是修复此问题的代码片段.对于每个元素，我们决定是否将其添加到总和中.如果元素允许我们的目标达到0，我们将1添加到可能性总数中，然后递归查看是否有任何其他方法可以在不添加当前正在判断的元素的情况下达到目标:
A = [2, 1, 1, 4]
def W(number, index):
if number < 0 or index < 0 :
return 0
elif number - A[index] == 0:
return 1 + W(number, index - 1)
else:
return W(number, index - 1) + W(number - A[index], index - 1)
print(W(1, 3)) # Prints 2