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$

2 Answers 2

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, 2020 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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .