# Disjoint Subset Sum Reduction (NP-Complete)

I am using past materials to review for an upcoming assignment and came across this question:

Disjoint Subset Sum:

Input: A set of integers S and a goal g(in the set of natural numbers)

Output: YES if there are at least two disjoint(non-overlapping) subsets of S where the elements of each subset sum to exactly to g otherwise NO

I need to prove that this is NP-Complete.

I know how to prove it is in NP. However, I am struggling with the reduction from subset sum to this problem. My initial thought was adding 0 and g to the set in subset sum to modify the input because if subsetsum had a subset that summed to g then the second disjoint subset must be 0 and g. The problem with this is that subset sum takes in a set of non-negative integers(according to the way I learned it) so 0 and g can already be in the set. I have tried other ways but I can't seem to account for any edge case that arises.

I think there is an edge case: adding 'g' to some subset S doesn't change if g already exists(so I think the reduction has to do with adding g)

Any help is appreciated! I wasn't able to find anything similar online(only the partition problem) so I'm asking here!

You are almost there. First of all it is useless to add $$0$$, even if it were allowed by the problem statement. Second, if the subset-sum instance is trivially a yes-instance because its set of integers already contains the target value (notice that you can detect this in polynomial time) then you can return any fixed yes-instance of disjoint subset-sum.
To summarize, if $$\langle S', g' \rangle$$ is an instance of subset-sum, a possible polynomial-time reduction to disjoint subset-sum returns the instance $$\langle S,g\rangle$$ where:
• If $$g' \in S'$$ then $$S =\{1, 2, 3\}$$ and $$g = 3$$;
• Otherwise ($$g' \not \in S'$$), $$S = S' \cup \{g'\}$$ and $$g = g'$$.
To see that this works, consider a yes-instance $$\langle S', g' \rangle$$ of subset-sum. If $$g' \in S'$$ then $$\langle S,g\rangle$$ is trivially a yes instance of disjoint subset-sum. If $$g' \not \in S'$$, then let $$S^* \subseteq S^*$$ be a set such that $$\sum_{s \in S^*} s = g'$$. A solution to the disjoint subset-sum problem is given by the two sets $$S^*$$ and $$\{g'\}$$.
Suppose now that $$\langle S,g\rangle$$ is a yes-instance of disjoint subset-sum. Then there are two disjoint sets $$S_1, S_2 \subseteq S$$ such that $$\sum_{s \in S_1} s = \sum_{s \in S_2} s = g = g'$$. Since at least one of $$S_1$$ and $$S_2$$ does not contain $$g'$$, this set is also a solution to the original subset-sum instance $$\langle S', g' \rangle$$.