20-CS-122-001 Computer Science II Spring 2012
Subset of Numbers

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Given: a list L=L[0],L[1],L[2],...,L[M] of integers plus an integer N.
Find: Whether a subset of L adds to N.

Idea:
    Consider all the Ns that are possible for the single number L[0]: just N=0 and N=L[0]. The first case corresponds to L[0] NOT being a solution and the second case corresponds to L[0] BEING the solution. Now consider L[0] and L[1] together. The possible Ns are N=0 (neither L[0] nor L[1] are in the solution), N=0+L[1] (the solution is just L[1]), N=0+L[0] (the solution is just L[0]), N=L[1]+L[2] (the solution is both). Now consider L[0], L[1], L[2]. Possible Ns are 0, L[0], L[1], L[2], L[0]+L[1], L[0]+L[2], L[1]+L[2], L[1]+L[2]+L[3].

The following is where this is going. Recall M+1 is the size of the list L. Construct a table with N columns and M+1 rows. Each element of the table will have value true or false: the value true in an element at row i, column j means there is some subset of the numbers L[0] to L[i] that sums to j. If true shows up in column N, return true, otherwise return false.

How to build this table? The 0th row has true in columns 0 and L[0] and false in all other columns. The element at column j of row 1 is true only if either the element at column j of row 0 is true or the element at column j-L[1] of row 0 is true - all other elements in row 1 are false. The element at column j of row 2 is true only if either the element at column j of row 1 is true or the element at column j-L[2] of row 1 is true - all other elements in row 2 are false.

In general: the element at column j of row i is true only if either the element at column j of row i-1 is true or the element at column j-L[i] of row i-1 is true - all other elements in row i are false.

Thus, the table can be built starting with row 0, then row 1, and so on until row M+1. The solution is in column N.