Possible recurrence relation error in Subset Sum: Ch. 3 section 8 pg. 114

[mousseinov]

page 114, section 3.8: In the pseudo code recurrence relation at the bottom of the page for subset sum modified for avoiding the case when t is negative, it says SS(i, t) = SS(i + 1, t) when t > X[i] in the third case, for that case wouldn't it be valid when t < X[i] rather than t > X[i], as that would make the t that is being passed in negative when doing SS(i, t - X[i]) which would automatically yield a False.

[echuber2]

The typo is in the recurrence relation rather than the pseudocode listing, but I think you're right.

There's also a typo in footnote 17 at the bottom of p. 115: "is not necessary bounded" should say "necessarily."

[mousseinov]

Sorry, yeah I meant to say the recurrence relation, not the pseudo code. Thank you!

[jeffgerickson]

Yes, "if t > X[i]" should be "if t < X[i]".