# Untitled

By: a guest on May 4th, 2012  |  syntax: None  |  size: 2.41 KB  |  hits: 30  |  expires: Never
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]