# Talk:Subset Sum

Isn't Problem B a special case of problem A? (Namely, deciding whether the answer in A is 0 or not, instead of actually finding it.) Not sure how that's relevant though, just an observation. Aboyner 14:13, 20 Dec 2005 (EST)

Yes, there are definitely overlaps, and I probably should put the more specific (and presumably easier to understand) first, since all "B" is asking is if the count is > 0..

Feel free to edit, I'm not sure what the best way to write things is either! --Larry 14:17, 20 Dec 2005 (EST)

## $a_{i}$ values

Are $a_{i}$ values supposed to not ever be lower than zero? What happens to equation $c(i,j)=c(i-1,j)+c(i,j-a_{i})$ when either $i-1$ or $j-a_{i}$ get below zero, or one is zero but the other is not (value $(0,0)$ is not reached yet)? If the answer to first question is "yes", then the answer to the second one is easy and should be incorporated to the text? I guess this is the case, otherwise it may result in an infinite number of different ways to get the final result.

It depends on the exact problem -- you're right in that there would be infinite number of different ways to get the final result if each $a_{i}$ can be used as many times. If each $a_{i}$ can only be used once, you can modify the recurrence slightly to make it work. I will change the problem to reflect that more accurately.

Larry 12:24, 17 February 2012 (EST)

## $k_{i}\in (0,1)$ ???

Last section: I believe you mean $k_{i}\in \{0,1\}$ rather than $k_{i}\in (0,1)$ .