There is a set A of positive/negative integers. We are given N numbers which are the sum of all its subsets. The task is to find the set A itself. Following is an example.
Input: 0 -2 4 5 2 3 9 7
Output: A = {-2 4 5}
For the case of positive integers, there is an O(n log n) solution suggested in this question. The algorithm
- Sorts the input.
- Takes the smallest element as a member of
A.- Builds all possible subset sums so far (possible in
O(n)) and removes them from input.- Repeats the above until the
log nnumbers ofAare found.
But I have no idea how to deal with negative numbers since the smallest number isn't necessarily in set A (take A = {-2, -3} as an example). Any ideas on how to solve this version of problem with negative numbers? Preferably still in O(n log n).
I just figured it out and Dave was on the right track.
The smallest value is the sum of the negative values. The differences between the values and the minimum are the sums of the absolute values of members of the set. You can find the absolute values in time O(n log(n)). Find any subset of the absolute values that sums to the absolute value of the minimum, reverse their signs, and you have an answer.
Note that there may be many valid answers.