用乘法求出子集的总和

Question

假设我们有一套

{a_1, a_2, a_3, ..., a_n}

目标是找到我们以下列方式创建的总和:我们找到长度为3的所有子集,然后将每个子集的元素相乘(对于{b_1, b_2, b_3}结果将是子集b_1*b_2*b_3).最后,我们总结了所有这些产品.

我正在寻找最短的时间执行算法.

例

SET: {3, 2, 1, 2}

Let S be our sum.

S = 3*2*1 + 3*2*2 + 2*1*2 + 3*1*2 = 28

Answer 1

这是一种O(n^2)方法:

sum = SUM(list)
answer = 0
for each i from 0 to n:
   sum -= list[i]
   remains = sum
   for each j from i+1 to n:
      remains -= list[j]
      answer += list[i] * list[j] * (remains)

这是有效的,因为对于每个两个元素,x,y您需要求和x*y*z(对于所有元素z),但所有可能z值的总和是SUM(list) - x - y.

所以,x*y*z1 + x*y*z2 + ... + x*y*z(n-2)你基本上做了,而不是做x*y*(z1 + ... + z(n-2))

编辑:由于@AbhishekBansal所提到的,仅仅在'尾部'中不会增加编辑的多次计数.您需要将每个元素仅与列表的"尾部"相乘,其中尾部是最后一个元素之后的所有元素x,y.