Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 4th, 2012  |  syntax: None  |  size: 2.41 KB  |  hits: 30  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. Subset sum recursively in Python
  2. subset_sum([-1,1,5,4],0)   # True
  3. subset_sum([-1,1,5,4],-3)  # False
  4.        
  5. def subset_sum(seq, target):
  6.     if target == 0:
  7.         return True
  8.     if seq[0] == target:
  9.         return True
  10.     if len(seq) > 1:
  11.         return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
  12.     return False
  13.        
  14. def subset_sum_mem(seq, target, mem=None ):
  15.     if not mem:
  16.         mem = {}
  17.     key=(len(seq),target)
  18.     if key not in mem:
  19.         if target == 0 or seq[0]==target:
  20.             mem[key] = True
  21.         if len(seq)>1:
  22.             mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
  23.         mem[key] = False
  24.  
  25.     return mem[key]
  26.        
  27. def positive_negative_sums(seq):
  28.     P, N = 0, 0
  29.     for e in seq:
  30.         if e >= 0:
  31.             P += e
  32.         else:
  33.             N += e
  34.     return P, N
  35.  
  36. def subset_sum(seq, s=0):
  37.     P, N = positive_negative_sums(seq)
  38.     if not seq or s < N or s > P:
  39.         return False
  40.     n, m = len(seq), P - N + 1
  41.     table = [[False] * m for x in xrange(n)]
  42.     table[0][seq[0]] = True
  43.     for i in xrange(1, n):
  44.         for j in xrange(N, P+1):
  45.             table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]]
  46.     return table[n-1][s]
  47.        
  48. def subset_sum(seq, target):
  49.     if target == 0:
  50.         return True
  51.  
  52.     for i in range(len(seq)):
  53.         if subset_sum(seq[:i] + seq[i+1:], target - seq[i]):
  54.             return True
  55.     return False
  56.        
  57. >>> subset_sum([-1,1,5,4], 0))
  58. True
  59. >>> subset_sum([-1,1,5,4], 10)
  60. True
  61. >>> subset_sum([-1,1,5,4], 4)
  62. True
  63. >>> subset_sum([-1,1,5,4], -3)
  64. False
  65. >>> subset_sum([-1,1,5,4], -4)
  66. False
  67.        
  68. from itertools import combinations
  69.  
  70. def com_subset_sum(seq, target):
  71.     if target == 0 or target in seq:
  72.         return True
  73.  
  74.     for r in range(2, len(seq)):
  75.         for subset in combinations(seq, r):
  76.             if sum(subset) == target:
  77.                 return True
  78.     return False
  79.        
  80. def subset_sum(seq, target):
  81.     left, right = seq[0], seq[1:]
  82.     return target in (0, left) or
  83.         (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target)))
  84.  
  85. def subset_sum_mem(seq, target, mem=None):
  86.     mem = mem or {}
  87.     key = (len(seq), target)
  88.     if key not in mem:
  89.         left, right = seq[0], seq[1:]
  90.         mem[key] = target in (0, left) or
  91.             (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem)))
  92.     return mem[key]
create a new version of this paste RAW Paste Data