title: Using recursion to solve the subset sum problem
body: <p>I want to calculate the number of subsets of the array <code>A = [2, 1, 1, 4]</code> that sum to <code>2</code>. There are 2 ways: <code>(A[0])</code> and <code>(A[1], A[2])</code>. My code for computing this is:</p>
  <pre><code> def W(number, index):
       A = [2, 1, 1, 4]
       if number &lt; 0 or index &lt; 0:
            return 0
       elif number==0:
            return 1
       else: 
            return W(number, index-1) + W(number - A[index], index)
  </code></pre>
  <p>Right now, when I call the function with <code>W(2,3)</code>, I get <code>4</code> instead of 2. My problem is that my code also calculates the possibility <code>(A[1], A[1])</code> and <code>(A[2], A[2])</code>. Is there any way to fix it while still using recursion?</p>