A partition problem

Since no one has answered yet...

An upper bound is obviously $2^n$.

A lower bound is $2^{\lfloor n/2\rfloor+1}$ (since there are these many subsets of $C=\{\lceil n/2 \rceil,...,n\}$, and any pair of distinct integers equal to or greater than $\lceil n/2 \rceil$ adds up to more than $n$, so any of these subsets qualifies for $A$).

I believe, in fact, that one can prove an upper bound of $2^{n/2}poly(n)$. The very informal reasoning is the following.

Consider all subsets of $C$ of cardinality $m$. In how many ways can I "extend" any generic one of them $S$ (solely) with elements from $\{1,...,\lceil n/2 \rceil-1\}$ without violating the no-sum-in-the-other-partition rule (I'll call these legal extensions)? Consider a "Poissonized" choice of $S$, where each element of $C$ is inserted in $S$ with probability $\gamma=m/|C|$ (so I don't get exactly cardinality $m$, but close enough, and I think everything can be formalized properly) and now consider an integer $p$ in $\{1,...,\lceil n/2 \rceil-1\}$. How likely is it that $p$ can be added? Let's think now of going through the numbers $\lceil n/2 \rceil, ..., n-p$; if for any such number $q$ one but not both of $q$ and $p+q$ are in $S$ then I can't add $p$ to $S$. What's the probability of being able to add $p$? Let's focus on $m<\lceil|C|/2\rceil$ i.e. $\gamma\lesssim \frac{1}{2}$, since it's easy to see that for $\gamma\gtrsim\frac{1}{2}$ the situation is symmetrical (also in terms of number of subsets with that cardinality). For each $q$, the probability of $p$ "surviving" $q$ is $\gamma(1-\gamma)$, so $p$ has on average a probability bounded away from $0$ of surviving the whole process if it's roughly between $n/2$ and $n/2-\frac{1}{\gamma}$, a probability a constant factor smaller on average if it's roughly between $n/2-\frac{1}{\gamma}$ and $n/2-\frac{2}{\gamma}$ and so on. All told, we can then expect to add $O(\frac{1}{\gamma})$ different numbers to $S$, and so extend it in $2^{O(\frac{1}{\gamma})}=2^{O(n/m)}$ ways (note that this is an upper bound).

Now, one could actually make an almost identical argument on the ways to extend subsets of $\{1, ...,\lceil n/2 \rceil-1\}$ with elements solely of $C$, showing that if one starts with cardinality $m$ one can extend a subset "legally" in $2^{O(\frac{1}{\gamma})}=2^{O(n/(m))}$ ways (again, an upper bound). Then, every subset of $\{1,...,n\}$ satisfies at least one of the following three properties:

1. It has at most $\frac{n}{2\lg(n)}$ elements.
2. It has at least half its elements in $C$.
3. It has at least half its elements outside $C$.

The subsets with property $0$ are at most $n^{\frac{n}{2\lg(n)}}=2^{n/2}$, so they won't budge the $2^{n/2}poly(n)$. The subsets of with property $1$ but without property $0$ are subsets of $C$ that were be extended in at most $2^{O(n/m)}$ ways with $m\geq \frac{n}{2\lg(n)}$ i.e. in at most $2^{O(\lg(n))}=poly(n)$ ways; we know that there are $O(2^{n/2})$ subsets of $C$, so the subsets with property $1$ but not property $0$ are at most $2^{n/2}poly(n)$, and the same can be said of those with property $2$ but not property $0$.