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?

Solution:

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 |