Subset Sum

Subset Sum

import random

rand_list = sorted([random.randint(-100,100) for _ in xrange(7)])
K = random.randint(0,200)

def subset_sum(lst,K):
    lst.sort()
    sz = len(lst)
    def subset_sum_helper(index,s):
        if index == sz or s >= K : return s == K
        return subset_sum_helper(index + 1, s) or subset_sum_helper(index + 1, s + lst[index])
    return subset_sum_helper(0 , 0 )

def subset_sum_dp(lst,K):
    ways = {0}
    lst.sort()
    for v in lst:
        t = set()
        for w in ways:
            nv = v+w
            if nv == K : return True
            if nv < K:
                t.add(v+w)
        ways.update(t)
    return False
    


print rand_list
print K
print subset_sum(rand_list,K)
print subset_sum_dp(rand_list,K)