Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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 –  Gerhard Paseman Jul 11 '12 at 18:29
    
Thanks Gerhard! That was very helpful. –  Victor Jul 11 '12 at 19:10
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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