Subset Sum with Endless Supplies
by Isai Damier

#=======================================================================
# 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 ) )