数组中所有可能组合的乘积之和
Sum of Product of All Possible Combinations in an Array
有一个包含 N 个元素的数组。我必须选择 K 个元素并将它们相乘，假设乘法的值为 M(k)。现在添加所有可能的 M(k)。假设总和为 S(k)。是否有可能在 O(N^2)[ 的时间复杂度中确定 S(k)（其中 1 <= k <= N）的所有值=21=]?
这个论坛有Python语言的解决方案，但我不知道Python，除此之外我希望这个问题得到普遍解决。
基本上你想要的是展开单项式的乘积
(1 + A[0] x) (1 + A[1] x) ... (1 + A[N-1] x)
并读出x, x^2, ..., x^N的系数。有一个简单的 O(N^2) 时间解决方案，它使用学校算法将每个因数一一相乘。
有一个包含 N 个元素的数组。我必须选择 K 个元素并将它们相乘，假设乘法的值为 M(k)。现在添加所有可能的 M(k)。假设总和为 S(k)。是否有可能在 O(N^2)[ 的时间复杂度中确定 S(k)（其中 1 <= k <= N）的所有值=21=]?
这个论坛有Python语言的解决方案，但我不知道Python，除此之外我希望这个问题得到普遍解决。
基本上你想要的是展开单项式的乘积
(1 + A[0] x) (1 + A[1] x) ... (1 + A[N-1] x)
并读出x, x^2, ..., x^N的系数。有一个简单的 O(N^2) 时间解决方案，它使用学校算法将每个因数一一相乘。