Partition Problem

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.