# Subset Sum with Endless Suppliesby Isai Damier, Android Engineer @ Google

```#=======================================================================
# Author: Isai Damier
# Title: Subset Sum with Endless Supplies
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Given a sequence S, with n positive numbers totaling to T, check
#   whether there exists a subsequence totaling to x, where x is less
#   than or equal to T. You may use any of the elements in S more than
#   once.
#
# Time-complexity: pseudo-polynomial: O(n*x)
# Space-complexity: O(x)
#
# Dynamic Programming Strategy:
#
#   We are not going to say too much here since this is essentially the
#   "Positive Subset Sum" problem. So we will wait right here as you
#   go read the "Positive Subset Sum" implementation.
#
#   Okay. So there is one distinction between the two problems: here you
#   may use each elements as many times as you need. So given the sequence
#   S={2,8,24}, we can reach 6 as 2+2+2 or 20 as 8+8+2+2.
#
#   To achieve this multiplicity, all we have to change is the direction
#   of the nested for-loop so that we end up with:
#
#     for(int e : S)
#       for(int i=0; i<=x; i++)
#         if(sum[i])
#           sum[i+e]=true;
#
#   The reason it's that simple is because the line "if(sum[i])" is
#   most of the time looking at multiples. For instance, during the first
#   pass of the outer for-loop (i.e. e=2), the second for-loop sets all
#   multiples of 2 to true. Manually run the example where S={2,8,24}
#   and x=18 if you still don't see it.
#=======================================================================
def subsetSumEndlessReuse( S, x ):
# preliminary
if x < 0 or x > sum( S ) :
return False

# algorithm
sum_list = [False] * ( x + 1 )
sum_list[0] = True
p = 0
while not sum_list[x] and p < len( S ):
e, q = S[p], 0
while not sum_list[x] and q <= x:
if q + e <= x and sum_list[q]:
sum_list[q + e] = True
q += 1
p += 1

return sum_list[x]
```
```import unittest
from dynamic_programming import SubsetSumWithMultipleSupplies as algorithm

class Test( unittest.TestCase ):

def testPositiveSubsetSum( self ):
S = [2, 8, 24]
for x in range( 24 + 8 + 2, -1, -2 ):
self.assertTrue( algorithm.subsetSumEndlessReuse( S, x ) )

for x in range( 24 + 8 + 2 - 1, 0, -2 ):
self.assertFalse( algorithm.subsetSumEndlessReuse( S, x ) )
```