Find sum for every possible add or multily operands Given a list of elements find total sum when addition and multiplication operands can be used between any two elements.
For e.g.,
given a list of elements as 1, 2 and 4. The operation goes as:
(1+2+4) = 7
(1+2*4) = 9
(1*2+4) = 6
(1*2*4) = 8
Total Sum = 7+9+6+8 = 30.
As the elements of list increases, the number of expression increases. How it can be done efficiently ?
 A: Assumption: 


*

*element of list are processed in a fixed order,

*parenthesis not allowed and usual PEMDAS order of operation.


Let $a_1, \ldots, a_n$ be the elements of the list. 
For any $k \in 1,2,\ldots, n$, let $\mathcal{E}_k$ be the collection of expressions that can be formed from the first $k$ elements $a_1, \ldots, a_k$ in given order using $+$ and $*$ operators only. 
Any expression $E$ in $\mathcal{E}_k$ can be broken down as a sum of terms.
Each term can be broken down as a product of factors. In our case, the factors are consecutive elements from the list $a_1, \ldots, a_k$. 
$$\underbrace{\verb/expression/}_{V(E)} = \underbrace{\verb/term/_1 + \verb/term/_2 + \cdots + \verb/term/_{m-1}}_{L(E)} + \underbrace{\verb/term/_m}_{R(E)}$$
Let $V(E)$ be the value of expression $E$, $L(E)$ be the value without the last term and $R(E)$ be the value of last term. Define
$$L_k = \sum_{E \in \mathcal{E}_k} L(E)
,\quad
R_k = \sum_{E \in \mathcal{E}_k} R(E)
\quad\text{ and }\quad V_k =  \sum_{E\in\mathcal{E}_k} V(E) = L_k + R_k
$$
The value we want is $V_n$.
Consider what happens when we attach $a_{k+1}$ to some expression $E$ in $\mathcal{E}_k$ to construct a new expression in $\mathcal{E}_{k+1}$. Notice
$$V(E + a_{k+1}) = (L(E) + R(E)) + a_{k+1} \quad\implies\quad
\begin{cases}
L(E + a_{k+1}) &= L(E) + R(E)\\
R(E + a_{k+1}) &= a_{k+1}
\end{cases}
$$
and
$$V(E * a_{k+1}) = L(E) + (R(E)*a_{k+1}) \quad\implies\quad
\begin{cases}
L(E * a_{k+1}) &= L(E)\\
R(E * a_{k+1}) &= R(E)a_{k+1}
\end{cases}$$
Summing over the $2^{k-1}$ expression $E$ from $\mathcal{E}_k$ and the two choices of operators, we obtain following recurrence relations:
$$\begin{array}{rll}
L_{k+1} &= (L_k + R_k) + L_k &= 2L_k + R_k\\
R_{k+1} &= 2^{k-1} a_{k+1} + R_{k}a_{k+1} &= a_{k+1}(2^{k-1}+R_k)
\end{array}
$$
Together with the initial condition $L_1 = 0, R_1 = a_1$, we can evaluate $L_n$ and $R_n$ recursively and deduce the value of $V_n = L_n + R_n$.
As an example, consider your list $(a_1, a_2, a_3) = (\color{red}{1},\color{brown}{2},\color{magenta}{4})$,
$$\begin{array}{rll}
R_1 = \color{red}{1} &\implies R_2 = \color{brown}{2}(2^{1-1} + \color{red}{1}) =  \color{green}{4}&\implies R_3 = \color{magenta}{4}(2^{2-1} + \color{green}{4}) = 24\\
L_1 = 0 &\implies L_2 = 2(0) + \color{red}{1} = \color{blue}{1} &\implies L_3 = 2(\color{blue}{1}) + \color{green}{4} = 6
\end{array}$$
As a result, $V_3 = L_3 + R_3 = 30$.
A: Let $X=\{x_1,...,x_n\}$ be a set and let $F=\{f_1,...,f_r\}$ be a set of operators for X. We have $i=1,...,r^{n-1}$ possible choices of results $y_i=x_1 f_{i_1}...x_{n-1}f_{i_{n-1}}x_n$ where $f_{i_1}...f_{i_{n-1}}$ is the $i$th choice. The final result is $\sum_{i=1}^{r^{n-1}} y_i$.
Within a symbolic solver, you just have to iterate for finding the answer.
