Reduce the problem \mathsf{SUBSETSUM} to the problem \mathsf{PARTITION} and prove that \mathsf{PARTITION} belongs to \mathbf{NP}.
Given a set of integers S (possibly with repetitions), determine whether S can be partitioned into two subsets S_1 and S_2 (i.e., each element of S belongs either to S_1 or to S_2, but not the two at the same time) such that
\sum_{x\in S_1} x = \sum_{x\in S_2}x\ .
Given a set of integers S (possibly with repetitions) and an integer k, determine whether there exists a subset A\subseteq S such that
\sum_{x\in A} x = k\ .
