如何按以下順序生成所有可能的總和？

Question

假設我有一個數組可以說[1,2,3,4]：

我想找到的總和如下：

首先我產生對像：

(1 2 3 4) 

(123)(4) 

(1)(234) 

(12)(34) 

(12)(3)(4) 

(1)(23)(4) 

(1)(2)(34) 

(1)(2)(3)(4) 

的然後ANS將是元件的總和在一組由該組的長度乘以（對於所有可能的基團）

例如，在裝置（123）（4），則總和將是

(1+2+3)*3 + (4)*1 

我只想要最後的總和，它是所有這些值的總和，而不是實際的組。我怎樣才能做到這一點？

我能夠首先產生所有可能的組，然後尋找和

但，因爲我只需要總和，而不是實際的羣體去做，有沒有更好的辦法？

Answer 1

安排的數量是2**(len(L)-1)。一個8個元素的列表產生了128種不同的安排。這是一個指數問題。您可以生成所有可能的解決方案，然後計算每個答案，或者即時計算每個答案。無論哪種方式，它仍然是exp。

def part1(L, start, lsum): 
    if start == len(L): 
     print lsum 
    else: 
     for i in range(start, len(L)): 
      left = sum(L[start:i+1]) * (i-start+1) 
      part1(L, i + 1, lsum + left) 

def part2(L, M, X, start): 
    if start == len(L): 
     M.append(X) 
     print sum([sum(x) * len(x) for x in X]) 
    else: 
     for i in range(start, len(L)): 
      part2(L, M, X + [L[start:i+1]], i + 1) 

例如：

>>> part1(L, 0, 0) 
10 
17 
15 
28 
13 
20 
22 
40 
>>> M = [] 
>>> part2(L, M, [], 0) 
10 
17 
15 
28 
13 
20 
22 
40 

編輯：爲O所有的和之和（N ** 3）

爲L = [1,2,3,4,5,6 ]

[[[1],     [2],   [3],   [4],   [5],   [6]], 
[[1],     [2],   [3],   [4],   [5, 6]], 
[[1],     [2],   [3],   [4, 5],       [6]], 
[[1],     [2],   [3],   [4, 5, 6]], 
[[1],     [2],   [3, 4],       [5],   [6]], 
[[1],     [2],   [3, 4],       [5, 6]], 
[[1],     [2],   [3, 4, 5],          [6]], 
[[1],     [2],   [3, 4, 5, 6]], 
[[1],     [2, 3],       [4],   [5],   [6]], 
[[1],     [2, 3],       [4],   [5, 6]], 
[[1],     [2, 3],       [4, 5],       [6]], 
[[1],     [2, 3],       [4, 5, 6]], 
[[1],     [2, 3, 4],          [5],   [6]], 
[[1],     [2, 3, 4],          [5, 6]], 
[[1],     [2, 3, 4, 5],             [6]], 
[[1],     [2, 3, 4, 5, 6]], 
[[1, 2],        [3],   [4],   [5],   [6]], 
[[1, 2],        [3],   [4],   [5, 6]], 
[[1, 2],        [3],   [4, 5],       [6]], 
[[1, 2],        [3],   [4, 5, 6]], 
[[1, 2],        [3, 4],       [5],   [6]], 
[[1, 2],        [3, 4],       [5, 6]], 
[[1, 2],        [3, 4, 5],          [6]], 
[[1, 2],        [3, 4, 5, 6]], 
[[1, 2, 3],           [4],   [5],   [6]], 
[[1, 2, 3],           [4],   [5, 6]], 
[[1, 2, 3],           [4, 5],       [6]], 
[[1, 2, 3],           [4, 5, 6]], 
[[1, 2, 3, 4],               [5],   [6]], 
[[1, 2, 3, 4],               [5, 6]], 
[[1, 2, 3, 4, 5],                  [6]], 
[[1, 2, 3, 4, 5, 6]]] 

似乎有一種模式。奇怪的情況是：將序列的第一個元素作爲排序集合的最小元素的集合有32個，但是其餘的都是16.對於列表中的每個元素，我將所有包含該元素作爲第一個排序元素。

def part3(L): 
    ret = 0 
    for i in range(len(L)): 
     p = 0 
     for k in range(len(L) - i - 1): 
      p += sum(L[i:i+k+1]) * (k+1) * 2**(len(L) - i - k - 2) 
     p += sum(L[i:]) * (len(L) - i) 
     ret += p * max(1, 2**(i-1)) 
    return ret 

edit2：把它降到O（n^2）你需要使用DP。建立一個和數表來計算O（1）中的每個和。你用S [i] = S [i-1] + L [i]和sum（L [a：b]）建立一個數組S [S] - S [a]。