If they're random, then you have no guarantee you can do it at all, e.g. say there's a number p such that p divides every number in your list. Then every possible sum must also be a multiple of p. Now, the probability of getting all even numbers is , and it gets much less likely as the divisors get larger, but it's a nit that has to be picked. (Nitpick to the nitpick: that's only guaranteed to be a problem if p is a power of 2, else modding by 2^32 will change the remainder mod p.)

I think it's a more interesting problem if you get to pick your set of numbers. Clearly you only need 32 of them: 1, 2, 4, 8, ..., 2^31. So if you're allowed to choose more, what's the best way to do it? Or maybe that's too easy to be interesting...but at least it's well-defined.