This reminds me of a DP (dynamic programming) technique I learned for USACO to solve the knapsack problem. The complexity is $O(n m)$, where $m$ is the number of elements and $n$ is the maximum value (in this case the sum of all the elements). If the average value of an element is $\bar{x}$, then the complexity is $O(n^2\bar{x})$, not too bad.

First I'll define our list of values and call it `weights`. Note that because of the way the algorithm works, our list needs to be sorted (conveniently `Union` returns a sorted list). Here I'm just choosing 10 random numbers between 0 and 100.

 weights = Union[RandomInteger[100, 10]];

Next I'll initialize our workspace array `dp`:

 dp = ConstantArray[False, Total[weights]];

At step `k` of the algorithm, `dp[[v]]` is `True` if `v` is a sum of some subset of the first `k` elements in the list.

Now, here's the meat of the code:

 Do[
 With[{w = weights[[k]]},
 Do[
 If[dp[[v - w]], dp[[v]] = True],
 {v, Total[Take[weights, k]], w + 1, -1}
 ];
 dp[[w]] = True;
 ],
 {k, Length[weights]}
 ]

At each step `k`, we loop over the array (index `v`). If `dp[[v-w]]` is `True`, that means that `v-w` is the sum of a subset of the elements. Therefore the value obtained by adding the current element `w` is also a subset, so we set `dp[[v]]` true. Note that this only works when we go backwards over the list, so that each of the `dp[[v-w]]` that we look at is for the previous step, so we don't add `w` multiple times (if you go forwards you get the making-change problem).

As for the bounds of the loop, we start at `Total[Take[weights, k]]`, the total of the weights used so far, since we know we can't make any values greater than the sum if each element can be added only once). We also start at `w + 1`, so that `v - w` is always at least `1`. Finally, after each loop we set `dp[[w]]` to `True`, since the single element `w` is a subset of the elements.

After the algorithm runs, `dp[[v]]` is `True` if `v` is the sum of a subset of `weights`. We can use this code to check our values:

 First /@ Position[dp, True] == 
 Union[Total /@ Subsets[weights, {1, \[Infinity]}]]

After verifying that the algorithm works correctly for you, you might try translating it to C or C++ as it will go a *lot* faster.

Update
-

I found out that using boolean arrays was extremely slow (something like $O(n^3 m^2)$ according to my tests). If we use `1` for `True` and `0` for `False` (like C) then Mathematica tries to use a packed array to hold `dp`, which is much faster. The updated code follows:

 dp = ConstantArray[0, Total[weights]];
 Do[
 With[{w = weights[[k]]},
 Do[
 If[dp[[v - w]] == 1, dp[[v]] = 1],
 {v, Total[Take[weights, k]], w + 1, -1}
 ];
 dp[[w]] = 1;
 ],
 {k, Length[weights]}
 ]
 dp = Thread[dp == 1];