Counting the solutions to a restricted 0-1 knapsack problem Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ :

Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is  represented by a fraction $\frac{p}{q}$ in its lowest terms. 

Output:  the number of 0-1 solutions (i.e. those having $s_i\in \{0,1\}$) to $s_1 + s_2 + \dots + s_n \leq s$.


  What is the counting complexity of $\mathsf{\#IDKNAP}$?


Let $k := \lfloor s \rfloor$.  The problem asks for the number of $n$-bit vectors with at most $k$ bits set to $1$. The solution is $\sum \limits_{i=0}^k \binom{n}{i}$, for which there is no closed form in general, 
and thus cannot be computed in polynomial time in the input size. 

So (I think) $\mathsf{\#IDKNAP}$ would be either $\mathsf{NP~Hard}$ or $\mathsf{\#P~Hard}$. It seems to be insufficiently general to encode arbitrary  $\#\mathsf{KNAPSACK}$ problems, which are $\mathsf{\#P~Hard}$. 
On the other hand, $\mathsf{\#IDKNAP}$ has exponentially less input size than general knapsacks, for which the weight vector $(w_1,\ldots,w_n)$ has at least $n$ bits.
There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$.  In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$.  Without loss of generality we can take $k \le n$ (for terms where $i&gt;n$ contribute nothing to the sum).  Also you can compute ${n \choose i}$ in time polynomial in $n$.  Therefore, the whole sum can be evaluated in time polynomial in $n$.  In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent.  This is exponential in the size of the input.  Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.