Question

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!

Answer 1

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.