等和子集

Question

我想计算一个集合S存在多少对不相交的子集S1和S2(S1 U S2可能不是S)，其中S1中的元素和=S2中的元素和。

假设我已经计算了所有可能的2^n子集的所有子集和。我如何找到有多少不相交的子集有相等的和。

对于一个和值a，我们能用有和a/2的子集的计数来解决这个问题吗？

例如:S={1,2,3,4}

以下是问题的链接:http://www.usaco.org/index.php?page=viewproblem2&cpid=139

Answer 1

[编辑：修正愚蠢的复杂性错误。谢谢卡什！]

实际上，我相信您需要使用这里描述的O(3^N)算法来回答这个问题--O(2^N)分区算法只足够好，可以枚举所有不相交的子集对，这些子集的并集是整个基础集。

正如我链接到的答案中所描述的，对于每个元素，您基本上要决定是否：

1. 将其放在第一组中，
2. 将其放入第二组，或
3. 忽略它。

考虑所有可能的方法，生成一个树，其中每个顶点有3个子：因此O(3^N)次。需要注意的一点是，如果您生成了一个解(S1，S2)，那么您不应该也计算该解(S2，S1):这可以通过在您构建它们时始终保持两个集合之间的不对称来实现，例如，强制执行S1中的最小元素必须始终小于S2中的最小元素。（这种非对称强制有一个很好的副作用，就是将执行时间减半：））

如果您预期集合中会有许多小数字，那么还有另一种可能的加速可供您使用：首先，将列表中的所有数字按递增顺序排序。选择一些最大值m，越大越好，但要足够小，使您能够负担得起一个m大小的整数数组。现在我们将把数字列表分成两个部分，我们将分别处理：一个最多等于m的初始数字列表（这个列表可能相当小），以及其余部分。假设前k<=n个数字适合第一个列表，并将此第一个列表称为SK。原始列表的其余部分我们将称之为“S”。

第二，像往常一样处理余数(S')，但不是只记录具有相等和的不相交子集的数目，只要s1'-S2'<=m，就将d[abs(S1'-S2')]加到解的总数中。这是因为我们知道有许多方法可以从具有这种差分的前k个元素建立一对不相交的子集--对于每一个子集对(Sk1,Sk2)，我们可以将Sk1或Sk2中较小的加到S1'或S2'中较大的，另一个加到另一个，最终得到一对具有相等和的不相交子集。