0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ What if $k$ is a number other than $\frac{n}{2}$? $\endgroup$
    – Ari
    Jul 29 '20 at 17:03
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.