## Subset Sum CLRS 35.5, Part 1

### May 27, 2014

We studied the subset sum problem — find the subset of a set of integers that sum to a given target — in two previous exercises; in both cases, we produced an exact answer, but took exponential time to do so. In today’s exercise, we will study a variant of the subset sum problem — find the subset of a set of integers that have the largest sum not exceeding a given target — that admits both exact and approximate answers; the exact answer runs in exponential time, though it is typically quite fast, but the approximate answer runs in linear time in the number of integers in the input set. Our solution is given by CLRS 35.5.

The exact solution uses two auxiliary functions. The function denoted by *L* + *x* adds *x* to each element of a list *L*. The function `merge-lists`

takes two sorted input lists and returns the merge of the two lists with duplicates removed. Then CLRS gives the algorithm as follows, where *S* is a sorted list of integers and *t* is the target:

EXACT-SUBSET-SUM(*S*,*t*)

1 *n* = |*S*|

2 *L*_{0} = ‹0›

3 **for** *i* = 1 **to** *n*

4 *L _{i}* = MERGE-LISTS(

*L*

_{i−1},

*L*

_{i−1}+

*x*)

5 remove from

*L*every element that is greater than

_{i}*t*

6

**return**the largest element in

*L*

_{n}The approximation algorithm adds a trimming step to the exact algorithm. The trimming step removes from the accumulating *L* list partial sums that are within a factor of 0 < δ < 1 such that any partial sum that is less than 1 + δ times its predecessor is removed. For instance, given *L* = ‹10, 11, 12, 15, 20, 21, 22, 23, 24, 29› and δ = 0.1, the trimmed *L*‘ = ‹10, 12, 15, 20, 23, 24›, where 11 is removed because it is within 10% of 10 and 21 and 22 are removed because they are within 10% of 20; `trim`

assumes that *L* = ‹*y*_{1}, *y*_{2},… *y*_{m}› is sorted:

TRIM(*L*,δ)

1 let *m* be the length of *L*

2 *L*‘ = ‹*y*_{1}›

3 *last* = *y*_{1}

4 **for** *i* = 2 **2** *m*

5 *if* *y*_{i} > *last* · (1 + δ) // *y*_{i} ≥ *last* because *L* is sorted

6 append *y*_{i} onto the end of *L*‘

7 *last* = *y*_{i}

8 **return** *L*‘

Then the `approx-subset-sum`

algorithm is the same as the `exact-subset-sum`

algorithm except that step *L _{i}* = TRIM(

*L*, ε/2

_{i}*n*) is inserted between steps 4 and 5, where the solution is within 0 < ε < 1 percent of the desired target.

Your task is to implement the two algorithms given above. 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.