Number of partitions of an integer subject to some restrictions

Question

Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and each of the elements of $S$ lie within the range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number of partitions of $n$ using only the elements from $S$ as summands (over all such possible sets).

For example, If $S$ is $\{1, 1, 2, 2\}$, there are $3$ ways in which $n=4$ may be partitioned using elements from $S$:

$2+2$

$1+1+2$

$1+1+2$

The sequence $1+1+2$ has repeated because we treat each element in $S$ as different. With $1+1$, We can either take $2$ at the 3rd position or $2$ at the $4th$ position in $S$ above. Another $S$ may be $\{1,1,1,1\}$ in which case there is only one partition of $n=4$ given by $1+1+1+1$.

There are $2^n$ subsets of $S$. But since only a few subsets might sum to $n$, I expect the bound to be asymptotically lower than $O(2^n)$.

Answer 1

It does not exceed ${n\choose \lceil n/2\rceil}$ by Sperner's theorem (the subsets with the same sum are not contained one in another). On the other hand, if $n$ is even and we get $n$ copies of 2, we get exactly ${n\choose n/2}$ subsets with sum $n$, so the bound is tight. If $n$ is odd, we may take 1 and $(n-1)$ copies of 2 to get ${n-1\choose (n-1)/2}$ subsets with sum $n$, which is worse than the above upper bound approximately by a factor of 2.