I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:
Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers of one is T and the other is 2T. The subsets do NOT have to be disjoint.
And I want to use the classic subset problem to prove this:
Subset Sum: Given a set S of integers and an integer T, determine whether there is a subset of S such that the sum of the numbers is T.
I'm slightly struggling with the reduction from Subset-Sum to 2-Subset-Sum, as simply adding to the set the double of each number and using the same T does not work, e.g S = {1,7,8,5} and S'={1,2,5,10,7,14,16} with T = 10 wouldn't work, as S' would return "true" and S should return "false".
Thank you.
Let $\sum S$ denote the sum of the elements in a set S and let $s= \sum S_1$.
Given an instance of $SubsetSum(S_1, T_1)$ construct an instance of $TwoSubsetSum(S_2, T_2)$ by setting $S_2 = S_1 \cup \{s-2T_1\}$ and $T_2 = s-T_1$
$SubsetSum(S_1, T_1) \Rightarrow TwoSubsetSum(S_2, T_2)$
$\quad$Suppose there exists $x \subseteq S_1$ such that $\sum x = T_1$
$\quad$Then $(S_1 - x) \subseteq S_2$ such that $\sum (S_1-x)=s-T_1$ and $S_2 \subseteq S_2$ such that $\sum S_2=2(s-T_1)$
$TwoSubsetSum(S_2, T_2) \Rightarrow SubsetSum(S_1, T_1)$
$\quad$Suppose there exists $x, y \in S_2$ such that $\sum x=s-T_1$ and $\sum y = 2(s-T_1)$
$\quad$If $(s-2T_1) \in x$, then $(x - \{s-2T_1\}) \subseteq S_1$ with $\sum(x - \{s-2T_1\})=T_1$
$\quad$If $(s-2T_1) \notin x$, then $x \subseteq S_1$ with $\sum x=T_1$
$\quad$In either case, there is a subset of $S_1$ such that the sum of the numbers is $T_1$