Question

Peter and John are great friends. They like to play games with numbers. This time, Peter has given John 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 in Python using brute force to help John with his problem.

INPUT

• The first line corresponds to N, the amount of numbers given by Peter
• 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:

7

7

3

6

1

10

11

4

20

Sample Output 1:

True

Sample Input 2:

4

1

2

3

4

2

Sample Output 2:

True

Sample Input 3:

5

2

1

5

8

10

4

Sample Output 3:

False

Sample Input 4:

5

92

16

27

72

96

303

Sample Output 4:

True

Sample Input 5:

8

82

36

46

91

42

3

57

61

294

Sample Output 5:

True

Write a program, test using stdin → stdout

Answer 1

def isSubsetSum(set, n, sum):
   subset =([[False for i in range(sum + 1)] for i in range(n + 1)])
   for i in range(n + 1):
       subset[i][0] = True
   for i in range(1, sum + 1):
       subset[0][i]= False
   for i in range(1, n + 1):
       for j in range(1, sum + 1):
           if j<set[i-1]:
               subset[i][j] = subset[i-1][j]
           if j>= set[i-1]:
               subset[i][j] = (subset[i-1][j] or subset[i - 1][j-set[i-1]])
   return subset[n][sum]
      

n = int(input())
set=[]
for i in range(0,n):
s = int(input())
set.append(s)
sum = int(input())

if (isSubsetSum(set, n, sum) == True):
print("True")
else:
print("False")