## 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*(*n*2^{n}). 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*(*n*2^{n}) time complexity, but builds up the solution in stages. A matrix has *n* rows and 2^{n} 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.