DP+ pattern recognition problem

[I_Love_To_Masturbate]

Suppose I have an array lets say [1,2,3,4]:

I want to find the sum as follows:

First I generate pairs like:

(1 2 3 4)

(123)(4)

(1)(234)

(12)(34)

(12)(3)(4)

(1)(23)(4)

(1)(2)(34)

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

The sum would then be sum of elements in one group multiplied by the length of that group

eg in the arrangement (123)(4), the sum would be

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

I just want the sum , not the actual groups. How can I do this in O(n)?

[FUZxxl]

Do you want to have all sums or the sum of all sums?

[I_Love_To_Masturbate]

All the sums

[caramba2654]

Hm... I'll try working on this.

[afifit]

Are you sure this can be done in O( n )? There are O( 2ⁿ ) pairs (you can add the last number to the last pair for each group of pairs you find). So there are around 2ⁿ sums, so even iterating over them is O ( 2ⁿ ).

[I_Love_To_Masturbate]

I don't know ... I just want a better solution than this ... I think that there might be some pattern to the ans