高效算法计算所有k产品的总和

Question

假如给你一个列表L的n数字和整数k<n.有没有一种有效的方法来计算k不同数字的所有产品的总和L？

举个例子,拿L=[1,3,4,6]和k=2.然后我要找的号码是

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

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

Answer 1

设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