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!
Best Answer
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.
Counting the number of different sums in other cases could turn out to be pretty hard, I don't expect a closed formula for this to exist. But an algorithm does exist, see here e.g.
Also see this question and its answers