# Complexity of Subset-Sum when the target sum is a constant

The Subset-Sum decision problem is:

Given a set of n non-negative integers S, is there a subset of S that sum to k? If S and k are inputs, the problem is known to be NP-Complete.

What about the case when k is not an input but a constant?
Is the problem still NP-Complete?

My thoughts are that if k is given, since the integers are all non-negative, we only need to consider subsets of at most k elements (ignoring elements that are zero). That means we only need to consider at most $n^k$ possibilities which is polynomial. So, the problem is not NP-Complete. Is my understanding correct?

Yes. Even better, there is a dynamical programming solution that uses $O(nk)$ steps.
The missing information here is that $O(n^k)$ and $O(nk)$ are both exponential runtimes. The definition of NP-complete specifies runtimes in terms of the number of bits in the input, not in terms of single integer inputs like $k$.
Note that it requires $\log k$ bits to specify $k$. Therefore if you 'spend' n bits on the array input and m bits on specifying $k$, the runtime is $O(nk) = O(n2^m)$.