title: Getting all subsets from subset sum problem on Python using Dynamic Programming
body: <p>I am trying to extract all subsets from a list of elements which add up to a certain value.</p>
  <p>Example -</p>
  <ul>
  <li>List = [1,3,4,5,6]</li>
  <li>Sum - 9</li>
  <li>Output Expected = [[3,6],[5,4]]</li>
  </ul>
  <p>Have tried different approaches and getting the expected output but on a huge list of elements it is taking a significant amount of time.
  Can this be optimized using Dynamic Programming or any other technique.</p>
  <p><strong>Approach-1</strong></p>
  <pre><code>def subset(array, num):
      result = []
      def find(arr, num, path=()):
          if not arr:
              return
          if arr[0] == num:
              result.append(path + (arr[0],))
          else:
              find(arr[1:], num - arr[0], path + (arr[0],))
              find(arr[1:], num, path)
      find(array, num)
      return result
  
  numbers = [2, 2, 1, 12, 15, 2, 3]
  x = 7
  subset(numbers,x)
  </code></pre>
  <p><strong>Approach-2</strong></p>
  <pre><code>def isSubsetSum(arr, subset, N, subsetSize, subsetSum, index , sum):
      global flag
      if (subsetSum == sum):
          flag = 1
          for i in range(0, subsetSize):
              print(subset[i], end = &quot; &quot;)
          print(&quot;&quot;)
      else:
          for i in range(index, N):
              subset[subsetSize] = arr[i]
              isSubsetSum(arr, subset, N, subsetSize + 1, 
                          subsetSum + arr[i], i + 1, sum)
  </code></pre>