# 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)

## ${\displaystyle a_{i}}$ values

Are ${\displaystyle a_{i}}$ values supposed to not ever be lower than zero? What happens to equation ${\displaystyle c(i,j)=c(i-1,j)+c(i,j-a_{i})}$ when either ${\displaystyle i-1}$ or ${\displaystyle j-a_{i}}$ get below zero, or one is zero but the other is not (value ${\displaystyle (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 ${\displaystyle a_{i}}$ can be used as many times. If each ${\displaystyle 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)

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

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