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

Question

有一组正/负整数

A

。我们给出了

N

数字，这些数字是其所有子集的总和。任务是找到集合

A

本身。以下是一个例子。

输入：

0 -2 4 5 2 3 9 7

输出：

A = {-2 4 5}

对于正整数的情况，

这个问题

中建议了一个O(n log n)解决方案。算法

1. 对输入进行排序。
2. 将最小的元素作为

   A

   的成员。
3. 构建到目前为止所有可能的子集总和（可能在

   O(n)

   中）并从输入中删除它们。
4. 重复上述操作，直到找到

   log n

   的

   A

   个数。

但我不知道如何处理负数，因为最小的数字不一定在集合

A

中（以

A = {-2, -3}

为例）。关于如何用负数解决这个版本的问题有什么想法吗？最好还在

O(n log n)

.

Answer 1

我刚刚弄明白了，戴夫走在了正确的轨道上。

最小值是负值之和。值与最小值之间的差异是集合成员的绝对值之和。你可以找到时间的绝对值

O(n log(n))

。找到总和为最小值绝对值的绝对值的任何子集，反转它们的符号，你就有了答案。

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

Answer 2

我无法证明@btilly 的回答总是有效，所以我会提供这个替代方案：

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

所以接下来的挑战就是隔离 A 的一个成员，然后对其余成员重复使用子集总和...

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

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