2. Subset Sum
algonotes
lecturenotes
Acknowledgements
Some of this material is borrowed from Jeff Erickson’s chapters on Recursion, Backtracking, and Dynamic Programming. Check them out for a more detailed comparison between recursive and memoized implementations.
The Problem
- The Subset Sum takes as input an array X of n positive integers and a target Y > 0.
- The output is
YES
if there is a subset of the array X[1 .. n] that sums to Y, andNO
otheriwse.