Ok, I think I have an answer:

Let $X_i = |\{\sum_J e_j, J \subset [1,2,..,i] \}|.$

Notice that: $Pr(X_i = 2X_{i-1}) \sim \frac{2^n - X_{i-1}^2}{2^n}$. (because, you need the new integer to be different from every difference of two partial sum of the previous integers). Then, if we suppose that $X_n \leq P(n)$ where $P$ is a polynomial, this probability tends to 1 as $n$ tends to $\infty$. (because $Pr(X_i = 2X_{i-1}) \geq \frac{2^n - P(n)^2}{2^n} \geq (1- \epsilon)$ for large enough $n$). But in that case, the probability that this will give us something above $P(n)$ is $1$ asymptotically. This lead us to a contradiction. Therefore, the case where $X_n$ is bounded by a polynomial is very unlikely. I think we can do the same (but we have to check carefully the details) for $X_n \leq 2^{n/2 - \delta}$ so the $Pr(X_n \leq 2^{n/2 - \delta}) \rightarrow 0$.

We can probably also relax the condition $Pr(X_i = 2X_{i-1})$ by $Pr(X_i = (1+\delta)X_{i-1})$, to prove something a little bit stronger.

I hope it was understandable, I writed this very quickly because of a lack of time.

Ok, I think I have an answer:

Let $X_i = |\{\sum_J e_j, J \subset [1,2,..,i] \}|.$

Notice that: $Pr(X_i = 2X_{i-1}) \sim \frac{2^n - X_{i-1}^2}{2^n}$. (because, you need the new integer to be different from every difference of two partial sum of the previous integers to double the number of different sums). Then, if we suppose that $X_n \leq P(n)$ where $P$ is a polynomial, this probability tends to 1 as $n$ tends to $\infty$. (because $Pr(X_i = 2X_{i-1}) \geq \frac{2^n - P(n)^2}{2^n} \geq (1- \epsilon)$ for large enough $n$). But in that case, the probability that this will give us something above $P(n)$ is $1$ asymptotically. This lead us to a contradiction. Therefore, the case where $X_n$ is bounded by a polynomial is very unlikely. I think we can do the same (but we have to check carefully the details) for $X_n \leq 2^{n/2 - \delta}$ so the $Pr(X_n \leq 2^{n/2 - \delta}) \rightarrow 0$.

We can probably also relax the condition $Pr(X_i = 2X_{i-1})$ by $Pr(X_i = (1+\delta)X_{i-1})$, to prove something a little bit stronger.

I hope it was understandable, I writed this very quickly because of a lack of time.

Ok, I think I have an answer:

Let $X_i = |\{\sum_J e_j, J \subset [1,2,..,i] \}|.$

Notice that: $Pr(X_i = 2X_{i-1}) \sim \frac{2^n - X_{i-1}^2}{2^n}$. (because, you need the new integer to be different from every difference of two partial sum of the previous integers). Then, if we suppose that $X_n \leq P(n)$ where $P$ is a polynomial, this probability tends to 1 as $n$ tends to $\infty$. (because $Pr(X_i = 2X_{i-1}) \geq \frac{2^n - P(n)^2}{2^n} \geq (1- \epsilon)$ for large enough $n$). But in that case, the probability that this will give us something above $P(n)$ is $1$ asymptotically. This lead us to a contradiction. Therefore, the case where $X_n$ is bounded by a polynomial is very unlikely. We can do the same for $X_n \leq 2^{n/2 - \delta}$ so the $Pr(X_n \leq 2^{n/2 - \delta}) \rightarrow 0$.

We can probably also relax the condition $Pr(X_i = 2X_{i-1})$ by $Pr(X_i = (1+\delta)X_{i-1})$, to prove something a little bit stronger.

I hope it was understandable, I writed this very quickly because of a lack of time.

Ok, I think I have an answer:

Let $X_i = |\{\sum_J e_j, J \subset [1,2,..,i] \}|.$

Notice that: $Pr(X_i = 2X_{i-1}) \sim \frac{2^n - X_{i-1}^2}{2^n}$. (because, you need the new integer to be different from every difference of two partial sum of the previous integers). Then, if we suppose that $X_n \leq P(n)$ where $P$ is a polynomial, this probability tends to 1 as $n$ tends to $\infty$. (because $Pr(X_i = 2X_{i-1}) \geq \frac{2^n - P(n)^2}{2^n} \geq (1- \epsilon)$ for large enough $n$). But in that case, the probability that this will give us something above $P(n)$ is $1$ asymptotically. This lead us to a contradiction. Therefore, the case where $X_n$ is bounded by a polynomial is very unlikely. I think we can do the same (but we have to check carefully the details) for $X_n \leq 2^{n/2 - \delta}$ so the $Pr(X_n \leq 2^{n/2 - \delta}) \rightarrow 0$.

We can probably also relax the condition $Pr(X_i = 2X_{i-1})$ by $Pr(X_i = (1+\delta)X_{i-1})$, to prove something a little bit stronger.

I hope it was understandable, I writed this very quickly because of a lack of time.