# subset sum problem when the number of integers in the sum is known

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!

-
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

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