The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.
The Partition problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.
Prove that the partition problem is NP-Complete using that SubsetSum so is it.
Any ideas?
Define your $\rm P{\small ARTITION}(S, K)$ problem as:
"Are there partitions $S_1, S_2$ of $S$ such that $|\text{sum}(S_1) - \text{sum}(S_2)| \leq K$, where $\text{sum}(S_i)$ is the sum of all elements of $S_i$?".
Then $\rm P {\small ARTITION}(S, 0)$ would mean $|\text{sum}(S_1) - \text{sum}(S_2)| \leq 0$ which is true only if $\text{sum}(S_1) = \text{sum}(S_2)$. Thus, given $S$ we could reduce the $\rm S{\small UBSET}(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements---$\rm P{\small ARTITION}(S, 0)$.
The reduction to the latter can be done as following:
Let $s=\text{sum(S)}$ and define a new set $S_{new} = S \cup \{2k − s\}$. We choose $2k-s$ since the sum of $S_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.
Now call (reduction!) $\rm P{\small ARTITION}(S_{new},0)$. If it returns YES/TRUE then $S_{new}$ can be partitioned into two sets $S_1$ and $S_2$ with sums equal to $k$. Also notice that either $S_1$ or $S_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S_1$ or $S_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.
