-
Notifications
You must be signed in to change notification settings - Fork 4
/
subsetSumProblem.py
66 lines (52 loc) · 1.87 KB
/
subsetSumProblem.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from Array import empty_2d_array
# Time Complexity: Exponential
def subset_sum_rec(elt_set, total_sum, n):
if total_sum == 0:
return True
if n == 0 and total_sum != 0:
return False
return subset_sum_rec(elt_set, total_sum, n-1) or subset_sum_rec(elt_set, total_sum-elt_set[n-1], n-1)
"""
elt_set = [2, 4, 1]
total_sum = 3
[
i 0 1 2 3 (sum)
0 [T, F, F, F],
2 1 [T, F, T, F],
4 2 [T, F, T, F],
1 3 [T, T, T, T]
(elt)
]
"""
# Time Complexity: O(n^2)
# Space Complexity: O(n^2)
def subset_sum_dp(elt_set, total_sum):
rows = len(elt_set) + 1; cols = total_sum + 1
table = empty_2d_array(rows, cols)
# Set each cell in first col as `True`, because total_sum = 0 can be formed if we have 0 in subset.
for row in xrange(0, rows):
table[row][0] = True
# Except (0, 0), set each cell in first row as `False`, because using subset {0} we can't form total_sum>0
for col in xrange(1, cols):
table[0][col] = False
for i_elt in xrange(1, rows):
for s in xrange(1, cols):
elt = elt_set[i_elt-1]
excl_elt = table[i_elt-1][s]
# If current elt > current sum, we can't include current elt in subset.
if elt > s:
table[i_elt][s] = excl_elt
else:
incl_elt = table[i_elt-1][s-elt]
table[i_elt][s] = excl_elt or incl_elt
#print table
return table[rows-1][cols-1]
if __name__ == '__main__':
elt_set = [2, 4, 1]
total_sum = 3
print "\n------- Using Recursion -------\n"
res = subset_sum_rec(elt_set, total_sum, len(elt_set))
print "Can we form a subset having sum {}? - {}".format(total_sum, res)
print "\n------- Using DP -------\n"
res = subset_sum_dp(elt_set, total_sum)
print "Can we form a subset having sum {}? - {}".format(total_sum, res)