20-CS-122-001 | Computer Science II | Spring 2012 |
---|---|---|
Subset of Numbers |
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. |