# Is it possible to easily count all the possible distinct sums from distinct numbers?

For example, given four distinct numbers $$5, 6, 7, 9$$ We have $$2^4-1$$ sums, $$5, 6, 7, 9, 11, 12, 14, 13, 15, 16, 18, 22, 20, 21, 27$$ which are the sums from the numbers.

But if given five distinct numbers $$5, 6, 7, 8, 9$$, then we see $$5 + 9 = 6 + 8$$, hence the possible distinct sums of them cannot be easily counted by $$2^5-1$$.

Is it possible to easily count all the possible distinct sums from distinct numbers? Thanks!

• $2^4$ and $2^5$ if you count $0$ as a sum too. – Henno Brandsma Sep 30 '18 at 6:06

It's rather easy to count the total number of possible sums this way. But the actually different sums is a different matter: the knapsack problem says it's NP hard to determine whether some number $$n$$ is among those sums for a concrete set of numbers.
For superincreasing sequences all sums will be different. This has been the idea of building a public key encryption system, in fact: to modify a superincreasing sequence so that we still keep the unique sums property (so we have the maximal number of sums). $$1,2,4,8, \ldots$$ is superincreasing.