title: Recursive program to get all subsets with given sum includes repetitions
body: <p>I am trying to write a program that takes as input:</p>
  
  <ol>
  <li>a list of allowed numbers (<code>arr</code>)</li>
  <li>a total (<code>sum</code>)</li>
  </ol>
  
  <p>It should return all the possible combinations of numbers in <code>arr</code> that add up to <code>sum</code>.</p>
  
  <p>This is what I have so far:</p>
  
  <pre><code>def printAllSubsetsRec(arr, v, sum):
      if sum == 0:
          return [v]
  
      if len(arr) == 0:
          return
  
      v1 = [] + v
      v1.append(arr[0])
      without_first = printAllSubsetsRec(arr[1:], v, sum)
      with_first = printAllSubsetsRec(arr[1:], v1, sum - arr[0])
      if with_first and without_first:
          return with_first + without_first
  
      elif with_first:
          return with_first
      elif without_first:
          return without_first
  
  def array_sums(arr, sum):
      v = []
      return printAllSubsetsRec(arr, v, sum)
  </code></pre>
  
  <p>The problem is that it doesn't return all the subsets including repetitions.</p>
  
  <p>For example:</p>
  
  <pre><code>print(array_sums([1,3,5],5))
  # [[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [3, 1, 1], [5]]
  </code></pre>
  
  <p>How can I do that?</p>