# Commits

committed e28513c

• Participants
• Parent commits 10b83af

# File greplin-challenge/subsets.py

` #!/usr/bin/env python2.6`
`+"""Subsets`
`+`
`+This is a naive solution which brute forces all subsets.  I verified it gave the correct results, then didn't think any more of it.`
`+"""`
` `
` import sys`
` import itertools`

# File greplin-challenge/subsets2.py

`+#!/usr/bin/env python2.6`
`+"""Subsets`
`+`
`+This is a dynamic solution which runs efficiently.  I did not think of this approach, but implemented it from the description at http://programmingpraxis.com/2010/11/09/subset-sums/.`
`+"""`
`+`
`+def solve(numbers):`
`+  """Solve sum of subsets for numbers.`
`+`
`+  numbers must be positive and in sorted order.`
`+  """`
`+  memo = {}`
`+  def f(stop, target):`
`+    """number of subsets of numbers[:stop] which sum to target"""`
`+    if stop == 0:  # empty set only matches if target is 0`
`+      return target == 0`
`+    if target == 0:  # only empty set matches`
`+      return 1`
`+`
`+    key = (stop, target)`
`+    if key in memo:`
`+      return memo[key]`
`+`
`+    result = f(stop - 1, target)  # without last`
`+    last = numbers[stop - 1]`
`+    if target >= last:`
`+      result += f(stop - 1, target - last)  # with last`
`+`
`+    memo[key] = result`
`+    return result`
`+`
`+  return sum(f(x, numbers[x]) for x in xrange(2, len(numbers)))`
`+`
`+`
`+def show(numbers):`
`+  print numbers`
`+  print "=", solve(numbers)`
`+  print`
`+`
`+show([1, 2, 3, 4, 6])`
`+show([3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99])`
`+`
`+`
`+# primes example from Praxis`
`+`
`+def primes(stop):`
`+  """Return sieve for primes 2..stop."""`
`+  sieve = [True] * stop`
`+  for x in xrange(2, stop):`
`+    if sieve[x]:`
`+      yield x`
`+      for n in xrange(2 * x, stop, x):`
`+        sieve[n] = False`
`+`
`+show(list(primes(2**10)))`