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,8,14,16}
with T = 10
wouldn't work, as S' would return "true" and S should return "false".
Thank you.