# Finding a reduction for two-Subset sum problem

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.

• Try reducing from the PARTITION problem instead of general SUBSET-SUM. – Yuval Filmus Jul 2 '17 at 9:27
• It might be easier with the Partition problem, but I specifically want from Subset-Sum (It's part of the question's requirement). – BAM Jul 2 '17 at 9:39
• In that case, you can compose the reduction from Subset-Sum to Partition and the reduction from Partition to your problem. Both are pretty simple. – Yuval Filmus Jul 2 '17 at 10:23
• Ok, thanks. Do you have an idea how to do the reduction directly though? It's definitely possible. – BAM Jul 2 '17 at 11:28
• Think about how you could reduce a problem in which you are given a set $S$ of integers and an integer $T$, and need to determine whether some subset of $S$ sums to $T$, to the same problem, but with $T$ forced to be 0. When constructing the instance of the second problem, think about what effect multiplying all numbers, or adding a constant to each number, has on its solutions. – j_random_hacker Jul 2 '17 at 12:58

There is a trivial reduction from Partition to your problem: given an instance $S$ of partition, construct the instance $(S,\frac{1}{2} \sum_{i \in S} i)$ of your problem. This shows that if you take any reduction from Subset-Sum to Partition, you immediately get a reduction from Subset-Sum to your problem. You can find the reduction from Subset-Sum to Partition in many places, or come up with it on your own.