Question: Given a set of integers, is there an algorithm that returns the sum of all the subsets? For example if $s = \{6, 3, -2\}$ then the algorithm returns $28$. I.e:

$$(-2) + (3) + (3-2) + 6 + (6-2) + (6+3) + (6+3-2) = 28$$

The runtime of this is $\mathcal{O}(2^n)$ though I believe: is there a quicker way to do this?

Thanks

Answer: 
Every element of the set occurs in half of the subsets of $s$, so in $2^{\lvert s\rvert-1}$ subsets (taking the complement gives a bijection between the subsets of $s$ containing $x$ and those not containing it). Therefore,

$$\sum\_{M \in \mathcal{P}(s)}\left(\sum\_{x\in M} x\right) = 2^{\lvert s\rvert-1}\cdot\sum\_{x\in s} x,$$

which computes the sum in $O(\lvert s\rvert)$ time (assuming the arithmetic operations take constant time).

Check: $s = \{6,3,-2\}$, $\lvert S\rvert = 3$, so

$$2^2\cdot (6+3-2) = 4\cdot 7 = 28.$$
You are generating the [Power set](http://en.wikipedia.org/wiki/Power_set) of some set $S$ with $n$ elements (denoted $\mathcal{P}(S)$) and then summing over all of the elements, so it would be impossible to have a runtime better than $\mathcal{O}(2^{n})$ because you need to generate and iterate over all of the $2^{n}$ possible subsets.