$(16$ pts$)$

$($Length of your answer: $1-2$ pages$)$

THREE$2$ONE$-$PARTITION Problem :

Instance: A finite set of positive integers $Z=\{Z_1,Z_2,$dots,$Z_n\}.$

Question: Is there a subset $Z^{\text{'}}$ of $Z$ such that

Sum of all numbers in $Z^{\text{'}}=3$ Sum of all numbers in $Z-Z^{\text{'}}$

SUM$-$OF$-$SUBSETS Problem

Instance: A finite set $A=\{a_1,a_2,$dots,$a_m\}$ and $M.$

Question: Is there a subset $A^{\text{'}}$ in $A$ s$.$t$.{\displaystyle \underset{a_{i}in{A}^{\text{'}}}{\overset{?}{}}}{a}_i=M?$

Given that THREE$2$ONE$-$PARTITION Problem is NP$-$Complete, prove that the SUM$-$OF$-$

SUBSETS Problem is NP$-$Complete by reducing THREE$2$ONE$-$PARTITION Problem to it$.$

$($a$)$ 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)$

$($b$)$ Define the transformation from the THREE$2$ONE$-$PARTITION Problem to the SUM$-$OF$-$

SUBSETS Problem and give the if$-$and$-$only$-$if proof.