python - 使用递归解决子集求和问题

Question

我想计算总和为 2 的数组 A = [2, 1, 1, 4] 的子集数。有两种方式:(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])。有没有办法在仍然使用递归的情况下修复它？

Answer 1

调用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