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:




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

then all the three sums


then all the four sums

until the sums which is all by sixteen


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?

  • $\begingroup$ 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? $\endgroup$ – babou Aug 9 '14 at 9:13
  • $\begingroup$ 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. $\endgroup$ – babou Aug 9 '14 at 9:59
  • $\begingroup$ 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. $\endgroup$ – babou Aug 9 '14 at 10:00
  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Aug 9 '14 at 10:38
  • $\begingroup$ @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. $\endgroup$ – InformedA Aug 17 '14 at 4:43

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.