子集的不同总和数

Question

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

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

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

Answer 1

使用动态规划，您可以找到中不同和的数量，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不同 s 的数量。Wf(W,n,3) == true

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