Subset Sum
March 27, 2012
The subset-sum problem asks you to find the subset of a set of integers that sums to a given target; for instance, given the set {267 439 869 961 1000 1153 1246 1598 1766 1922} and target 5842, the subset {869 961 1000 1246 1766} sums to 5842. This is a well-known NP problem, and the standard solution via dynamic programming takes time O(n2n). The basic idea is straight forward: generate a list of subsets, compute the sum of each, and return the one that sums to the target.
The dynamic programming solution has the same O(n2n) time complexity, but builds up the solution in stages. A matrix has n rows and 2n columns; the rows are marked with the n input values, the columns are marked with the various subset-sums, and each cell contains a list of items from the n values up to the current row that sums to the column total. We’ll look at an example: find the subset of items from {1 -3 4 2} that sums to 0. After the first element of the list is considered, the first row has two columns, the null column that we ignore and the column 1:
| 1 | |
| 1 | 1 |
With the second row, there are four columns: the null column that we ignore, and columns -3, 1, and 2:
| -3 | 1 | 2 | |
| 1 | 1 | ||
| -3 | -3 | 1 | -3 1 |
When we add the third row, there are eight columns: the null column that we ignore, the six columns -3, -2, 1, 2, 4, and 5, and a hidden column for 1, which can be formed in two different ways, as 1 by itself and as the sum of -3 and 4:
| -3 | -2 | 1 | 2 | 4 | 5 | |
| 1 | 1 | |||||
| -3 | -3 | -3 1 | 1 | |||
| 4 | -3 | -3 1 | 1 | -3 1 4 | 4 | 1 4 |
When we add the fourth row, there are sixteen columns, but only eleven appear in the table: -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, and 7. We ignore the null column, and there are four hidden columns corresponding to the following sum-pairs, only one of which appears in the table (it doesn’t matter which): 1 = -3 + 4, 2 = -3 + 1 + 4, 1 + 2 = -3 + 2 + 4, and 4 = -3 + 1 + 2 + 4:
| -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 1 | ||||||||||
| -3 | -3 | -3 1 | 1 | ||||||||
| 4 | -3 | -3 1 | 1 | -3 1 4 | 4 | 1 4 | |||||
| 2 | -3 | -3 1 | -3 2 | -3 1 2 | 1 | -3 1 4 | 1 2 | 4 | 1 4 | 2 4 | 1 2 4 |
The solution is the subset {-3 1 2}. I apologize for my lack of table-fu.
Your task is to write a function that solves the subset-sum problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 