问具有相等和的子集

EN

编辑:修正了愚蠢的复杂性错误。谢谢kash!

实际上，我相信您需要使用O(3^n)算法described here来回答这个问题-- O(2^n)划分算法只能很好地枚举所有不相交的子集对，这些子集的并集就是整个基本集。

正如我链接的答案中所描述的，对于每个元素，您实际上是在决定是否：

1. 把它放在第一组，
2. 把它放在第二组，或者
3. 忽略它。

考虑到每种可能的方法，生成一个树，其中每个顶点都有3个子节点:因此O(3^n)时间。要注意的一件事是，如果你生成一个解决方案( S1，S2)，那么你不应该计算解决方案( S2，S1)：这可以通过在构建时始终保持两个集合之间的不对称性来实现，例如，强制S1中的最小元素必须始终小于S2中的最小元素。(这种不对称执行有一个很好的副作用，可以将执行时间减半：)

针对一种特殊(但在实践中可能很常见)情况的加速

如果您希望集合中有许多较小的数字，还有另一种可能的加速:首先，按升序对列表中的所有数字进行排序。选择一些最大值m，越大越好，但足够小，可以承受m大小的整数数组。我们现在将数字列表分为两部分，我们将分别处理:最初的数字列表，其和最多为m(该列表可能非常小)，其余的部分。假设前k个<= n个数字适合第一个列表，并将其称为第一个列表Sk。原始列表的其余部分我们将称为S‘。

首先，将整数的大小为m的数组d[]初始化为全0，并照常解决Sk的问题--但不是只记录具有相等和的不相交子集的数量，而是为由前k个数字形成的每对不相交子集Sk1和Sk2递增d[abs(|Sk1| - |Sk2|)]。(同时增加d[0]以计算Sk1 = Sk2 ={}时的情况。)这个想法是，在第一阶段完成后，d[i]将记录从S的前k个元素生成具有i差的两个不相交子集的方式的数量。

其次，像往常一样处理余数(S') --但不是只记录具有相等和的不相交子集的数量，每当|S1'| - |S2'| <= m时，将d[abs(|S1'| - |S2'|)]添加到解决方案的总数中。这是因为我们知道有许多方法可以从具有这种差异的前k个元素构建一对不相交的子集-对于这些子集对(Sk1, Sk2)中的每一个，我们可以将Sk1或Sk2中较小的一个添加到S1‘或S2’中的较大者，而将另一个添加到另一个中，以得到一对具有相等和的不相交的子集。

这是一个clojure解决方案。

它将s定义为1，2，3，4的集合，然后将所有子集定义为大小为1-3的所有集合的列表

一旦定义了所有子集，它就会查看所有的子集对，并只选择不相等、不与原始集并集以及其和相等的子集对

(require 'clojure.set)
(use 'clojure.math.combinatorics)

(def s #{1, 2, 3, 4})
(def subsets (mapcat #(combinations s %) (take 3 (iterate inc 1))))

(for [x all-subsets y all-subsets 
          :when (and (= (reduce + x) (reduce + y)) 
                     (not= s (clojure.set/union (set x) (set y))) 
                     (not= x y))] 
      [x y])

生成以下内容：

([(3) (1 2)] [(4) (1 3)] [(1 2) (3)] [(1 3) (4)])