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

Question

我想计算数组 A = [2, 1, 1, 4] 中加和为 2 的子集数量。共有 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])。是否有任何方法可以修复它，同时仍然使用递归？

- AlphaList

---

请注意，当您使用数组中的数字（将其减少）时，您不希望再次重复使用它 :) - E. Shcherbo

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

- BrokenBenchmark

---

“W(4,3)”应该是2，而“W(5,3)”也应该是2吧？ - Cubix48

W(1, 3)打印出1，但我认为应该是2，因为A[1]和A[2]都有效。 - D Malan

好的，已编辑。 - BrokenBenchmark

对于您提出的第一点：原始代码没有这个问题（特别是您提到的W(2,0)情况），因为在原始代码中，当我们从数组中使用数字时，索引永远不会改变。 因此，对W（2,0）的调用会分为两个调用-W（2，-1）和W（0，0）。第二个分支返回1。注意：我是在谈论作者的原始代码。 - E. Shcherbo

我再次编辑以澄清该错误与递归结构有关。感谢您在解释中指出这个问题。 :) - BrokenBenchmark

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))

输出

2
2
2
2
2
2
2
1

- quamrana