3. Consider the Partition problem: Given a set S of n positive integers, decide whether it can

be partitioned into two subsets S₁ and S₂ whose sums are equal.

Prove that Partition is NP-Complete. You will need to show both that the problem is in NP,

and that it is NP-Hard. For the latter, use a reduction from the Subset-Sum problem, which

is known to be NP-Complete