4
$\begingroup$

Hi everyone, I'm trying to solve a variation of the subset sum problem (http://en.wikipedia.org/wiki/Subset_sum_problem) in which all the integers that I'm using are strictly positive and (most importantly) I know in advance the number of integers that make up the sum. Does anyone know if there is any solution that takes advantage of the second fact? For example, for the set {7,2,5,1} and target sum = 7, both {7} and {2,5} are solutions but if I already know that my solution needs to use only 2 integers, then only {2,5} is a valid solution. Thanks in advance!

$\endgroup$
2
  • 1
    $\begingroup$ I suspect that you can reduce the general problem to your version as follows: given an arbitrary set T and target sum s, add big number M to each element of T, and perhaps a few more M's as members, and make kM+s the target sum for a reasonable choice of k. Gerhard "Ask Me About System Design" Pasman, 2012.07.11 $\endgroup$ Jul 11, 2012 at 18:29
  • $\begingroup$ $k$-SUM can be solved in polynomial time using algorithms that are generalizations of the solutions to 2-SUM (for $k$ even) and 3-SUM (for $k$ odd), respectively. See this link for more details. $\endgroup$ Jun 7, 2017 at 23:04

1 Answer 1

4
$\begingroup$

Garey and Johnson, page 223: given a finite set $A$ and a positive integer $s(a)$ for each $a$ in $A$, the question, is there a subset $A'$ of $A$ such that $$\sum_{a\in A'}s(a)=\sum_{a\in A-A'}s(a)$$ is NP-complete. It remains NP-complete even if we require $\\#(A')=\\#(A)/2$.

Of course, if you know that the number of integers making up the sum is small, e.g., 2, then the number of possible sets of that size is polynomial in the size of that problem, and just looking at all the subsets of that size is a polynomial time algorithm. The result above suggests that if the number of integers making up the sum is proportional to the total number of integers, so there are exponentially many subsets to try, then NP-completeness comes in.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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