Algorithm to recover a set given the sums of all its subsets

Question

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

1. Sorts the input.
2. Takes the smallest element as a member of A.
3. Builds all possible subset sums so far (possible in O(n)) and removes them from input.
4. Repeats the above until the log n numbers of A are 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).

Answer 1

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.

Answer 2

If you can find any member x of the set A then it's easy to separate all the subset sums into the ones that include x and the ones that don't. If x is positive, for example, then the smallest sum does not include x, and if you add x to it, you get the corresponding sum that does include x. The smallest remaining sum then does not include x, etc...

So the challenge is then just to isolate a member of A, and then repeat using the subset sums for the remaining members...

Note that any valid list of sums will contain 0, and the difference between the two smallest sums will be the same as the difference between the two largest sums, and that difference will be the smallest absolute value of a member of A.

To determine whether that smallest member is positive or negative, try separating the sums according to the above procedure and choose positive or negative according to which choice leaves a 0 in the remaining list.

Here's an implementation and a little test in python:

def getSubsetSums(lst):
    sums = [0]
    for x in lst:
        sums = sums + [x+y for y in sums]
    return sums

def getSetFromSubsetSums(sums):
    lst=[]
    sums = sorted(sums)
    while(len(sums) > 1):
        diff = sums[1] - sums[0]
        A=[]
        B=[]
        bmatched=0
        Ahas0 = False
        for x in sums:
            if bmatched < len(B) and x == B[bmatched]:
                bmatched += 1
                continue
            A.append(x)
            B.append(x+diff)
            if (x==0):
                Ahas0 = True
        if (Ahas0):
            sums = A
            lst.append(diff)
        else:
            sums = B
            lst.append(-diff)
    return lst


sums = getSubsetSums([9,1,-6,-4])
print(sums)
members = getSetFromSubsetSums(sums)
print(members)

sums = getSubsetSums([-2, 4, 5])
print(sums)
members = getSetFromSubsetSums(sums)
print(members)

[0, 9, 1, 10, -6, 3, -5, 4, -4, 5, -3, 6, -10, -1, -9, 0]
[1, -4, -6, 9]
[0, -2, 4, 2, 5, 3, 9, 7]
[-2, 4, 5]