1
$\begingroup$

I am doing some research where I have a List containing numbers. For example

{5,10,98,22,13,15}

What is a fast algorithm to calculate all possible sums and differences from these? Eventually I will want to do the same thing for a list of 400+ numbers.

Some examples in the final set

index0+index1=5+10=15
index0+index3+index4=5+22+13=40
index0+index2-index5=5+98-15=88
index3-index4=22-13=9

What I am thinking now is 3 for loops. One to move through the array, one to keep track of how many numbers to skip, and one for the number of skips. But that seems slow.

Ahh I guess my answer is unsolvable bc of P=NP. I see from here: https://en.wikipedia.org/wiki/Subset_sum_problem

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ (What are the conditions that would allow you to not compute each and every subset's sum? given the empty set has sum 0, how do you get the sum of every subset of cardinality 1?) $\endgroup$ – greybeard Nov 17 '16 at 17:57
  • 1
    $\begingroup$ There are about $3^n$ different sums or differences that can be written out of $n$ numbers, assuming no repeats. In you example $3^6=729$ and $3^{400}$ is a lot. $\endgroup$ – Karolis Juodelė Nov 17 '16 at 18:08
  • $\begingroup$ @KarolisJuodelė oh thanks for that. I guess this task is impossible. What about just addition or just subtraction. Still as big? $\endgroup$ – Seth Kitchen Nov 17 '16 at 18:11
  • 1
    $\begingroup$ @SethKitchen, just addition would be about $2^n$ which is still a lot. The problem is not that there are too many operations, but too many terms. For example, if you just wanted sums of pairs of numbers (so, not 5+22+13), you'd only get about $n^2$ which is a lot less. $\endgroup$ – Karolis Juodelė Nov 17 '16 at 19:10
  • $\begingroup$ Short answer, what you are trying to do is probably misguided. You need to rethink the algorithm to something with a lot less calculations or subsets $\endgroup$ – fernando.reyes Nov 17 '16 at 21:46

Your Answer

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

Browse other questions tagged or ask your own question.