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