Forming a set of positive integers with each subset summing uniquely

Question

Let N be a positive integer.

We want a set of positive integers M, |M| = N, such that any subset sums to a unique number.

In general there may be a lot of numbers. Setting each number to 1, and we couldn't distinguish which 1's added up to, say, 3. If M is powers of 2, then that may work (for N=3):

M = {1,2,4}

1
2
4
1+2=3
4+1=5
4+2=6
4+1+2=7

The problem is now the numbers use more bits. Can we do it in less bits?

Answer 1

You can always build one incrementally like below:

• Let begin with $S_0=\varnothing$
• Chose a number $a_{n+1}$ strictly greater than $\sum\limits_{i\in S_n} a_i$
• Define $S_{n+1}=S_n\cup\{a_{n+1}\}$

Then $S_N$ satisfies your request.

Note that in case of base-$2$ numbers, you start with $1$, select $2>1$ then $4>1+2$ then $8>1+2+4$, and so on... At each step you have selected the minimal number available, so base-$2$ numbers will give the minimal $\max(S_N)$ for a given $N$.