|August 1999||Perl Hardware Store||Slide #36|
Input is a list of numbers
Question: Can we divide the list into two subsets that have the same sum?
Equivalent problem: Given a target sum, can we fnud a subset of elements that add up to it?
If target sum is 0, the empty set is a solution
Otherwise, if list is empty, there is no solution.
Otherwise, suppose target sum is s.
Suppose first element is x.
See if the rest of the elements can hit a target of s or s-x.
If so we win; if not, we lose.
|Next||Copyright © 1998 M-J. Dominus|