给定集合所有子集的和来恢复集合的算法

Question

存在一个正/负整数的集合A。给出了CCD_ 2数，它是其所有子集的和。任务是查找集合A本身。下面是一个例子。

输入：0 -2 4 5 2 3 9 7
输出：A = {-2 4 5}

对于正整数的情况，在这个问题中有一个O(n log n)的解决方案。算法

1. 对输入进行排序
2. 将最小的元素作为A的成员
3. 构建到目前为止所有可能的子集和(在O(n)中可能)，并从输入中删除它们
4. 重复上述步骤，直到找到A的log n编号

但我不知道如何处理负数，因为最小的数字不一定在集合A中(以A = {-2, -3}为例)。关于如何用负数解决这个问题，有什么想法吗？优选仍在CCD_ 13中。

Answer 1

我刚刚想明白了，Dave走在了正确的轨道上。

最小的值是负值的总和。值和最小值之间的差是集合中成员的绝对值之和。您可以找到时间O(n log(n))中的绝对值。找到与最小值的绝对值相加的绝对值的任何子集，反转它们的符号，你就有了答案。

请注意，可能有许多有效的答案。

Answer 2

如果你能找到集合A的任何成员x，那么很容易将所有的子集和分为包括x的和不包括的。例如，如果x为正，则最小的和不包括x，如果将N0添加到其中，则得到包含x的相应和。最小的剩余和则不包括x等。

因此，挑战是只隔离A的一个成员，然后重复使用剩余成员的子集和。。。

注意，任何有效的和列表都将包含0，并且两个最小和之间的差将与两个最大和之间的差值相同，并且该差值将是A的成员的最小绝对值。

要确定最小成员是正成员还是负成员，请尝试根据上述过程分离和，并根据在剩余列表中留下0的选项选择正成员或负成员。

以下是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]