高效算法打印长度为2到n + 1的所有可能子序列中元素的总和

Question

我将以一个示例开始。假设我们有大小的数组与元件a，b和c等：（其中a，b和c一些数值）

| 1 | 2 | 3 |
| a | C | ç|

（假设索引从1开始，如上面的的例子）

现在，所有可能的长度增加的亚序列是：

所以所需的元件的产品，在这些索引的总和，即，ab+bc+ac

对于长度我们仅增加一子序列，也就是123 abc应打印。
对于长度为我们没有序列，从而0被印刷，并且程序终止。

所以对于给定阵列输出将是：

ab+bc+ac,abc,0 

因此，例如，如果元件a，b和c为1，2和3分别然后输出应为11,6,0

类似地，对于大小的数组与元件A，b，C，d的输出将是：

ab+ac+ad+bc+bd+cd,abc+abd+acd+bcd,abcd,0 

等等......

现在很明显蛮力对于大数值的数组大小来说太低效了。我想知道是否有一个有效的算法来计算给定大小的数组的输出？

编辑1：我试图找到一个模式。例如，对于大小数组：

The first value we need is :(ab+ac+bc)+d(a+b+c)= ab+ac+ad+bc+bd+cd (Take A=ab+ac+bd) then the second value we need is:(abc) +d(A) = abc+abd+acd+bcd(B=abc) then the third value we need is : (0) +d(B) = abcd(Let's take 0 as C) then the fourth value we need is: +d(C) = 0

但它仍然需要大量的运算，我想不出来实现这一种有效的方式。

编辑2：我的问题是不同的，那么this，因为：

1. 我不需要所有可能的排列。我需要从长度2到n + 1的所有可能的递增子序列。
2. 我也并不需要打印的所有可能的这样的序列，我只需要（上文所解释）由此获得的值，因此我寻找一些数学概念和/或一些动态规划方法来解决这个问题有效率的。
3. 注意我正在找到基于索引值的所有可能的这种增加子序列的集合，然后根据上述那些索引位置处的值进行计算。

Answer 1

由于似乎已经消失的帖子指出，一种方法是获得递归关系。设S（n，k）为序列索引的数组元素乘积长度为k的增长子序列（1..n）之和。这样的子序列要么以n结尾，要么以n结尾。在第一种情况下，它是1..n-1和{n}的长度为k-1的子序列的连接。在第二种情况下，它是长度为k的1..n-1的子序列。因此：

S(n,k) = S(n-1,k) + A[n] * S(n-1,k-1) 

对于这个总是有道理，我们需要增加：

S(n,0) = 1 
S(n,m) = 0 for m>n