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.