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
On
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.$$
On
This can also be solved using a basic generating function technique. The ordinary generating function $f(z)$ where $[z^q] f(z)$ represents the number of times the sum $q$ occured among the subsets is given by $$f(z) = \prod_{x\in S} (1+z^x).$$ We want to turn $[z^q] f(z)$ into $q$, so we differentiate and set $z=1$ to obtain $$\left. f'(z)\right|_{z=1} = \left. \prod_{x\in S} (1+z^x)\times \sum_{x\in S} \frac{xz^{x-1}}{1+z^x} \right|_{z=1} = 2^{|S|} \times \sum_{x\in S}\frac{x}{2} = 2^{|S|-1} \sum_{x\in S} x.$$
You are generating the 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.