# Number of subsets that add up to a given number

I have a subset $S=\{x_1, x_2, x_3, ... x_m\}$ with $m$ elements in it. Each of these elements is between $1$ and $m^2$. Given an instance of this problem and a sum, $y$, I want to place an upper bound on the number of subsets of $S$ that can sum up to $y$. Any crude polynomial upper bound would work for me. (I need this upper bound for some proof I am constructing for a cryptography problem).

-
Seen this? –  J. M. is back. May 8 '11 at 13:11
@J.M. This variation of subset sum is not NP complete. –  AnkurVijay May 8 '11 at 13:13
Just checking. :) –  J. M. is back. May 8 '11 at 13:17
@Shreevatsa no i was hoping for a polynomial lower bound, but as yuval has explained, there's no such bound in general. –  AnkurVijay May 10 '11 at 2:55
I mean polynomial upper bound for a general instance –  AnkurVijay May 10 '11 at 3:09

If all elements are equal to $1$ and $y = m/2$ then the number of subsets is $$\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right).$$
Here's an example with all elements different. Let $S = \{1,\ldots,m\}$ and $y = (m+1)m/4$. The number of subsets is at least $$\binom{m/2}{m/4} = \Theta\left(\frac{2^{m/2}}{\sqrt{m}}\right).$$
Right, thanks. Also now i see that since the size of the domain is $2^m$ and the size of the range is $m^3$ (the elements can only sum up to at most $m^3$) the average number of preimages is also exponential. –  AnkurVijay May 10 '11 at 2:52