Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
Seen this? – J. M. 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. 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
up vote 4 down vote accepted

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).$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.