计算所有 k 乘积之和的高效算法

假设给你一个列表L of n数字和整数k<n。有没有一种有效的方法来计算所有乘积的总和k中的不同数字L?

举个例子，以L=[1,3,4,6] and k=2。那么我要找的号码是

1*3 + 1*4 + 1*6 + 3*4 + 3*6 + 4*6.

你能想出一种避免生成所有大小子集的方法吗k?

令 F(X,k,n) 为数组 X 的前 n 个元素的 k 乘积和。

F(X,k,n) = F(X,k,n-1)+F(X,k-1,n-1)*X[n]

您可以使用动态规划来解决这个问题。复杂度 = O(kn)。

F(X,k,n) 的结束条件： 当 n=k F(X,k,k) = X[1]* X[2]*...*X[n]

更多细节：

F(X,1,1) = X[1]
F(X,1,i) = F(X,1,i-1)+X[i] for i=2...n 

For j=2..n:
    For i = 1..k:
        if i<j:
            F(X,i,j) = F(X,i,j-1)+F(X,i-1,j-1)*X[j]
        else if i==j:
            F(X,i,j) = F(X,i-1,j-1)*X[j]
        else:
            pass