# I need a set that enables me to identify specific containing elements by any summation of any of its subsets (see example to understand)

My question is more practically understood by example. I need a set A that behaves like the one below:

Set A: {1,3,5}

Set B (all subsets of A): {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5}

Set C (summations of each element of B): {1}, {3}, {5}, {4}, {6}, {8}, {9}

Because every element of C is of unique value (that's the criteria), what I have is: every element of C identifies a specific combination of elements of A. If I am given 4, I know it's the sum of the specific elements 1 and 3 and no other possible combination of elements, and so forth for any given element of C.

To create a set A of 3 elements is easy, but I need the largest possible set A that contains only 2 digit natural numbers (from 01 to 99) matching this criteria. I need also to be able to find the matching elements of A from any given element of C (if I'm given 9 I need to know it refers to the elements 1+3+5 and so forth for any given sum).

Can anyone help me?

-

See OEIS sequence A096858. The 8-element set {40,60,71,77,80,82,83,84} has all its subset sums distinct, so this beats Alex's 7-element answer.

-
Awesome too! Thanks. –  juanpazos Aug 20 '14 at 4:52

Use the powers of $2$: $\{1, 2, 4, 8, 16, 32, 64\}$. Each subset sums to a unique number between $0$ and $127$, and it's easy to convert back just by calculating the binary (base 2) representation of the given number.

Edit: As Robert Israel's answer shows, the powers of $2$ are not necessarily optimal if you maximize the size of a set satisfying your condition with all elements below a certain bound (100 in your case). However, they are optimal in the reverse sense: if you specify the size of the set you want and try to minimize the size of the largest element.

Edit 2: Oops, that's also wrong. At least I can say with complete confidence that if you want a set of size $n$ with distinct subset sums and you want to minimize the largest sum (i.e. the sum of the whole list), then the first $n$ powers of $2$ are best (You'll need $2^n$ distinct sums, and each sum must be at least $0$, so the largest one must be at least $2^n-1$. The first $n$ powers of $2$ sum to exactly $2^n-1$). It's also hard to beat them for simplicity of the algorithm to translate the sum back to the subset.

-
If you specify size $7$, $\{20,31,37,40,42,43,44\}$ beats your $\{1,2,4,8,16,32,64\}$. If you specify size 8, $\{ 40,60,71,77,80,82,83,84\}$ beats $\{1,2,4,8,16,32,64,128\}$. –  Robert Israel Aug 20 '14 at 3:21
Ah, darn, you're right. –  Alex Kruckman Aug 20 '14 at 3:22