Using recursion to solve the subset sum problem-CodePudding

I want to calculate the number of subsets of the array A = [2, 1, 1, 4] that sum to 2. There are 2 ways: (A[0]) and (A[1], A[2]). My code for computing this is:

 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)

Right now, when I call the function with W(2,3), I get 4 instead of 2. My problem is that my code also calculates the possibility (A[1], A[1]) and (A[2], A[2]). Is there any way to fix it while still using recursion?

CodePudding user response：

The call to W(number - A[index], index) should be W(number - A[index], index - 1); otherwise, you allow for the possibility of double-counting an element in your subset sum.

Here is a code snippet that fixes this issue. For each element, we decide whether or not to add it to our sum. If the element allows our target to reach 0, we add 1 to our total count of possibilities, then recurse to see if there are any other ways to reach the target without adding the element we're currently examining:

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

CodePudding user response：

This code seems to work for cases finding sums of 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)

Testcases:

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

Output