The Partition Problem: Reducing to prove NP-Completeness


I am struggling with the below problem. Curious to hear any guidance.


The Partition Problem is the following:

$ \textbf{Instance:}$ A (multi-)set of numbers $ S = \{a_1, a_2, \ldots , a_n \}$ .

$ \textbf{Question:}$ Can $ S$ be partitioned into two (multi-)sets $ A$ and $ B$ such that the sum of the numbers in $ A$ is equal to the sum of the numbers in $ B$ ?

Prove that the Partition Problem is NP-complete.


Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Anyone able to help shed some light on this? Also, any explanation in plain english (maybe with some notation) would be greatly appreciated as I’m struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

Thank you in advance!