'''

SUM-OF-SUBSETS Problem

Instance: A finite set A = {a1,a2,....,am} and M

Question: Is there A in A s.t. ai in A'ai= M?

Given that the TWO2ONE-Partition problem is NP-complete, prove that the SUM-OF-SUBSETS

the problem is NP-complete by reducing the TWO2ONE-partition problem to it.

1. Give a nondeterministic polynomial time algorithm for the SUM-OF-SUBSETS problem.

(Use Guess statements in your solution, e.g Guess({0,1}) returns 0 or 1)

'''

Algorithm

:

1. Non-deterministic algorithm for SUM-OF-SUBSETS

For every element randomly Guess if it is part of subset

Guess(ai in subset)

1 if Yes (O(m))

0 if No (O(m))

check if sum of selected elements which have Guess( ) == 1, is M

if Yes, return True and this is the solution

if No, repeat above

Write the working code in Python for above algorithm?