# Complexity of Subset Sum where the size of the subset is specified

I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.

Given a subset $$S$$ of positive integers and integers $$k>0$$ and $$N>0$$, is there a subset $$T\subset S$$ such that $$|T|=k$$ and the members of $$T$$ sum to $$N$$ ?

All of the formulations of subset sum that I've seen don't specify $$k$$ so I'm wondering if this problem can be solved in polynomial time. If $$k$$ is fixed for all instances, then I know that the problem is in P and solvable by brute force in $$O(n^k)$$ time. However, I'm allowing $$k$$ to vary from instance to instance.

There are $$\binom{n}{k}$$ $$k$$-subsets of an $$n$$ set, and $$\binom{n}{k} = n (n - 1) \dotsm (n - k + 1) / k!$$, which is $$O(n^k)$$, as you observe. The brute force complexity is a bit more (need to add up the numbers too and check), but that is ballpark.
This is polynomial for any fixed $$k$$, but not polynomial in $$n$$ if e.g. $$k = n / 2$$ (that is the Partition problem, known NP-complete).
• What if $k$ is a number other than $\frac{n}{2}$?
As vonbrand said, if $$k$$ is a number other than $$\frac{n}{2}$$ it doesn't change much. Your problem is in $${\sf{P}}$$ as long as $$k$$ is a fixed number which does not depend on $$n$$.
You can try and show it is $$\sf{NPC}$$ by polynomial reduction from Partition (which is known to be NP complete).