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!