Question

Michael and Mary are great friends. They like to play games with numbers. This time, Michael has given Mary a list of numbers and given him the task of determining if it is possible to choose a subset of them such that they sum is equal to another given number.

Build an algorithm using dynamic programming to help Mary with his problem.

INPUT

• The first line corresponds to N, the amount of numbers given by Michael
• The next N lines contain each of the numbers
• The last line contains the desired sum

OUTPUT

• True or False (Whether is possible to obtain the desired sum or not)

Sample Input 1:

39
15
88
3
43
40
100
45
34
89
10
17
70
14
63
92
24
64
6
42
12
81
34
38
63
35
77
67
80
5
58
46
17
67
21
73
10
49
21
54
128

Sample Output 1:

True

Sample Input 2:

30
72
21
33
6
72
53
71
28
66
92
90
73
33
10
70
25
96
82
85
53
58
61
76
20
85
4
1
7
34
76
670

Sample Output 2:

True

Sample Input 3:

35
8
63
89
6
83
78
31
5
46
95
59
73
98
47
43
16
44
50
32
5
77
23
30
44
69
94
24
14
50
99
82
90
1
21
25
557

Sample Output 3:

True

Sample Input 4:

38
2
24
70
51
24
51
98
9
81
55
11
50
94
42
91
94
8
64
86
20
25
34
100
65
30
49
99
47
63
20
3
61
5
100
86
22
94
60
1766

Sample Output 4:

True

Sample Input 5:

21
29
53
31
74
21
57
35
67
10
86
60
46
17
52
38
21
14
51
26
12
86
647

Sample Output 5:

True

Write a program, test using stdin → stdout


**Note: it would be very useful if the code is solved in Python or C++, Thanks**

Answer 1

Python code:

def Subset_sum(arr,n,sum):
#base cases...
if(sum == 0):
return True
if(n == 0):
return False

if(arr[n-1]>sum):
return Subset_sum(arr,n-1,sum)

return Subset_sum(arr,n-1,sum) or Subset_sum(arr,n-1,sum-arr[n-1])

if __name__ == '__main__':
N = int(input())
li = []
for i in range(N):
li.append(int(input()))
s = int(input())
print(Subset_sum(li,N,s))

for every given test cases output is comming True .. u check it again