How to calculate number of possibilities?-CodePudding

(this is homework) I want to calculate amount of ways getting total number 2 of array A=[2, 1, 1, 4]. There are 2 ways = (A[0]) and (A[1],A[2]). My code(written in Python) for calculating that 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 ways 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 the algorithm is still dynamic/recursive?

CodePudding user response：

There are two issues with your code:

Your code (at some point) makes a recursive call to W(2, 0). Then, it makes a recursive call to W(0, -1). At this point, number is 0, but the index is negative, so 0 rather than 1 is returned, and this possibility is never counted. To resolve this issue, you should return as soon as you realize that 0 can be reached with the current element, rather than making an additional recursive call. (Note that I'm assuming, based on the number < 0 check, that the elements in the array are all strictly positive.)
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 both of these issues:

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