c - 子集的不同总和的数量

Question

我有一组 N，对于 N>3，不同的整数，问题是找到给定集合的 3 个子集的所有不同的和。3 子集是基数为 3 的子集。

我知道愚蠢的方法是对所有可能的总和进行三次搜索，然后整理出所有重复项。有没有更有效的方法来做到这一点？我正在用 C 编程。

编辑：如果说元素的数量增加了，我想知道一个通​​用的更快的算法。

Answer 1

如果您怀疑您可能有很多重复的总和，那么您可以首先计算所有不同的 2 子集总和，并且对于您找到的每个不同的 2 子集总和，跟踪您找到的哪一对给了您总和。如果你所有的数字都是不同的，那么如果你找到另一对给你相同的总和，你应该将总和标记为“多个”，如果你愿意，你可以删除你为它存储的那对。现在你有一组 2 子集和，每个和要么有一对存储在一起，要么被标记为“多个”。对于每个 2 子集总和，如果它被标记为“多个”，那么您遍历原始集中的所有数字并记录您可以通过将每个数字添加到 2 子集总和来形成的所有 3 子集总和。否则，如果 2 子集总和未标记为“倍数” 并且您有一对 (a,b) 与之关联，然后您执行相同的操作，只是在迭代原始数字集时跳过 a 和 b。这就是您获得所有不同的 3 子集总和的方式。如果你有 n 个数字并且它们产生 N 个不同的 2 子集和，那么如果你在算法的两个阶段使用哈希表来检测重复项，那么这种方法的复杂度是 O(nN)，这可能比 brute 要好得多强制 O(n^3 log n)，特别是如果你有一组相当密集的整数。

Answer 2

使用动态编程，您可以找到中不同和的数量O(n*MAX)，其中MAX是数组中的最大值。

让我们看一下递归函数：

f(W,n,i) = f(W,n-1,i) OR (i != 0 ? f(W-item(n),n-1,i-1) : false)
f(0,0,0) = true
f(W,n,0) = false (W != 0)
f(W,0,i) = false (W != 0)
f(W,n,i) = false (W < 0)
(I have a feeling I forgot another failing base clause, so make sure if I didn't)

现在，如果你使用动态编程构建这个自下而上的方法W=3*MAX，你的答案基本上就是W它们的不同 s的数量f(W,n,3) == true。

建立表格将是O(MAX*3 * n * 3) = O(MAX*n)，计算不同 s 数量的后处理阶段W给出所需的总和是O(MAX)，因此解决方案仍然存在O(MAX * n)