高效算法打印長度爲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