子集的不同总和数

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

我知道愚蠢的方法是对所有可能的总和进行立方搜索,然后整理所有重复项 . 有没有更有效的方法来做到这一点?我在C编程

编辑:我想知道一般的更快的算法,如果说元素的数量增加 .

回答(2)

2 years ago

使用动态编程,您可以在 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)

现在,如果你使用动态编程自下而上 Build 这个,最多 W=3*MAX ,你的答案基本上是他们 f(W,n,3) == true 的不同 W 的数量 .

构建表将是 O(MAX*3 * n * 3) = O(MAX*n) ,计算给出所需总和的不同 W 的数量的后处理阶段是 O(MAX) ,因此解决方案仍为 O(MAX * n)

2 years ago

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