Even with k=0, the problem is still NP-complete.

Are you referring to the "pseudo-polynomial" trick where you maintain a bit vector of partial sums?

Now that I think about it, it was a sequence of integers (looking for sub-sequences), not a set.

To be pendantic with terminology, if you take a sequence and remove some elements, what you're left with is a subsequence. If you take a sequence and you select some contiguous elements, what you get is a substring. So "amqz" is a subsequence of the alphabet but not a substring. "lmnop" is a substring and a subsequence.