# Compute sums of all subsets of some words

We have $16$ words of given length, let's say $W_1,...,W_{16}$ and and i want to make an one dimensional matrice that will contain all the possible sums of $W_i$'s, for example:

$W_1,W_2,...,W_{16}$

$W_1+W_2,W_1+W_3,...,W_1+W_{16}$

$W_2+W_3,...,W_2+W_{16}$

and so on, all the by two sums...

then all the three sums

$W_1+W_2+W_3,...,W_1+W_2+W_{16}$

then all the four sums

until the sums which is all by sixteen

$W_1+W_2+...+W_{16}$.

Is there a faster way for example, than using a triple $for$ to make all the possible by three sums and in general n fors to make all the by n sums?

• Does the number 16 ring a bell? Do you really think this is just a C++ programming exercise? Before walking your C++ path, you are probably supposed to plan the trip. Does your course include a little bit of algorithmic complexity? – babou Aug 9 '14 at 9:13
• I do not know the algorithm. But I can guess a bit what it should look like (I might be wrong). This seems much like a homework, which we are not supposed to answer too readily (it does not help education). Another point is that this site answers general computer science questions, not questions about a specific programming languages, unless they are examples of a general programming issue. So we may give you hints, as I did, but will try to avoid straights answers on what looks like homework. – babou Aug 9 '14 at 9:59
• This said, as further hint, I would try to see what the problem looks like with one or two numbers much smaller than 16. Preferably numbers that shares one of 16 's main characteristic. – babou Aug 9 '14 at 10:00
• Note that generating $2^{16}$ values will take at least $2^{16}$ steps, unless you can generate multiple values in a single step. Usually it will take multiple steps per value. But you may be able to reduce the number of steps per value by cleverly reusing values computed earlier. – FrankW Aug 9 '14 at 10:38
• @FrankW I don't understand, you should still need at least $2^{16}$ steps. You don't save steps by generating multiple values at a time. What is true is that you can save the number of addition operations invoked if you reused previously computed values. – InformedA Aug 17 '14 at 4:43

## 1 Answer

If you think that there are much fewer than $2^{16}$ sums, you can try the following approach. Iteratively compute a sorted list of all partial sums of the first $k$ values. Given this list for some $k$, add to all sums in the list $W_{k+1}$, and then merge the two lists like in Mergesort, removing duplicates. The total complexity should be asymptotic to the number of distinct partial sums.