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

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)；否则，您允许 double-counting 子集总和中的一个元素的可能性。

这是修复此问题的代码片段。对于每个元素，我们决定是否将其添加到我们的总和中。如果该元素允许我们的目标达到 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

Answer 2

此代码似乎适用于求和为 1..8 的情况：

A = [2, 1, 1, 4]

def W(number, index):
     if number == 0:
          return 1
     elif number < 0 or index < 0:
          return 0
     else:
         return W(number, index-1) + W(number - A[index], index - 1)

测试用例：

print(W(1, 3))
print(W(2, 3))
print(W(3, 3))
print(W(4, 3))
print(W(5, 3))
print(W(6, 3))
print(W(7, 3))
print(W(8, 3))

输出

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

Using recursion to solve the subset sum problem

python

algorithm

recursion

dynamic