Q:

Number of subsum of a given set of integers

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural:
Given n integers $(e_i)$ chosen (randomly) between $1$ and $2^n$, define $A = \{ \sum_I e_i, \forall I \subset [1,..,n] \}$.
The question is to estimate the size of $A$. If we take $\forall i, e_i = 1$, this size of $A$ equals $n+1$, if we take $\forall i, e_i = 2^i$, the size becomes $2^n$. I would guess that in general, it is very unlikely to have a polynomial size for $A$, but I can't prove anything.
If some results about the expectancy $|A|$, distribution, or anything is known, I would be very happy to have the links or explanations; or if you have any ideas to solve the problem, of course.
Thanks in advance!

A:

Do you want to know about specific $n$ values or asymptotics? 
In the event that $e_i=e_j,$  $|A| \le 2^{n}-2^{n-2}$ otherwise it seems highly likely that it is larger than that and, in any case, that $|A| \gt 2^{n-1}.$ The chance of having some $e_i=e_j$ is about $4.3\%$ for $n=10$ but $1-\prod_{j=1}^{19}(1-\frac{j}{2^{20}}) \approx 0.018\%$ for $n=20.$
The chance of having a case of $e_i+e_j=e_k$ is larger but still goes to $0$ as $n$ increases. If that does happen then $|A| \le 2^n-2^{n-3}$
In $1000$ trials with $n=10$ There were $40$ cases of $e_i=e_j$ and of these $|A|$ ranged from $552$ to $762.$ It the other $960$ cases (with the $e_i$ distinct) the sums ranged from  $628$ to $1012.$ 
In $100$ trials with $N=20$ there were, as expected, no cases of $e_i=e_j.$ The values of $|A|$ ranged between $2^{20}-2^{17.19}$ and $2^{20}-2^{16.02}.$
LATER  If you just want a lower bound which grows faster than any polynomial then I will propose $\sqrt{2}^N=2^{N/2}.$ This is of course terrible since the few experiments always had $|A| \gt 2^{N-1}.$ But lets look at the probability that if we just look at $e_1,e_2,\cdots,e_m$ with $2m \le N$ we have all $2^m$ partial sums unique. If there are two sets $I,J$ with $\sum_Ie_i=\sum_Je_j$ then there are two disjoint sets $I,J$ with this property (delete the common elements from both the old $I$ and old $J$.) To get one of these potential disjoint pairs $I,J$ we would split the indices $1,2,\cdot,m$ into three classes: 

used in $I$
used in $J$ and
used in neither. 

There are $3^m$ ways to do this (actually less than half this since we can ignore any possibility with $I$ or $J$ empty and we don't care which is $I$ and which is $J$.) The probability that a particular split gives equal sums is less than $2^{-N}$ since the maximum element can be one of $2^N$ values but at best, just one  of these  makes that split work. So the probability that at least one split gives equal sums is less than $\frac{3^m}{2^N}.$ Putting $m=N/2$ gives the probability of this failure at $\left(\frac{\sqrt{3}}{2}\right)^N$ which goes to $0$ exponentially quickly.

