algorithm - 用乘法求子集的和

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 中最后一个元素之后的所有元素。