Skip to content

Instantly share code, notes, and snippets.

@st0le

st0le/Subset Sum DP

Created June 4, 2013 21:51
Show Gist options
  • Save st0le/5709928 to your computer and use it in GitHub Desktop.
Save st0le/5709928 to your computer and use it in GitHub Desktop.
Download ZIP
Subset Sum DP
Raw
Subset Sum DP
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment