Skip to content

Commit ddace72

Browse files
authored
Subset_sum_dynamic programming
Initial File
1 parent 0cee48f commit ddace72

1 file changed

Lines changed: 23 additions & 0 deletions

File tree

Subset_sum_dynamic programming

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
def issubset(set,n,sum):
2+
subset=[[False for i in range(sum+1)]for i in range(n+1)]
3+
4+
for i in range(n+1):
5+
subset[i][0]=True
6+
for j in range(sum+1):
7+
subset[0][j]=False
8+
9+
for i in range(n+1):
10+
for j in range(sum+1):
11+
if j<set[i-1]:
12+
subset[i][j]=subset[i-1][j]
13+
if j>=set[i-1]:
14+
subset[i][j]= (subset[i-1][j] or subset[i-1][j-set[i-1]])
15+
return subset[n][sum]
16+
17+
set = [2, 3, 4, 5]
18+
sum = 20
19+
n = len(set)
20+
if issubset(set, n, sum):
21+
print("True")
22+
else:
23+
print("False")

0 commit comments

Comments
 (0)