## Subset Sum, Meet In The Middle

### March 30, 2012

This isn’t hard. We split the list, then apply the previous algorithm on the first half, then apply the previous algorithm on the second half. It does get messy because we put the whole thing in one big function:

```(define (subset-sum-mitm xs t)   (let-values (((f) (make-hash identity = #f 997))                ((b) (make-hash identity = #f 997))                ((front back) (split xs)))     (let loop1 ((front front))       (if (pair? front)           (let loop2 ((ys (cons (cons 0 (list)) (f 'enlist))))             (cond ((null? ys) (loop1 (cdr front)))                   ((= (+ (car front) (caar ys)) t)                     (cons (car front) (cdar ys)))                   (else (f 'insert (+ (car front) (caar ys))                                    (cons (car front) (cdar ys)))                         (loop2 (cdr ys)))))           (let loop3 ((back back))             (if (null? back) #f               (let loop4 ((ys (cons (cons 0 (list)) (b 'enlist))))                 (cond ((null? ys) (loop3 (cdr back)))                       ((f 'lookup (- t (car back) (caar ys))) =&gt;                         (lambda (x)                           (append (list (car back))                                   (cdar ys) x)))                       (else (b 'insert (+ (car back) (caar ys))                                        (cons (car back) (cdar ys)))                             (loop4 (cdr ys)))))))))))```

Here’s an example that shows the time improvement in the two algorithms:

```> (define ys '(267 439 869 961 1000 1153 1246 1598 1766 1922)) > (time (subset-sum ys 5842)) (time (subset-sum ys ...))     2 collections     125 ms elapsed cpu time, including 16 ms collecting     0 ms elapsed real time, including 0 ms collecting     7706816 bytes allocated, including 8325712 bytes reclaimed (1766 1246 1000 961 869) > (time (subset-sum-mitm ys 5842)) (time (subset-sum-mitm ys ...))     no collections     0 ms elapsed cpu time     0 ms elapsed real time     98584 bytes allocated (1766 1246 1000 961 869)```

We used hash tables and the `identity` function as in the previous example, as well as a `split` function, shown at codepad, that uses the tortoise-and-hare algorithm to split a list into front and back halves. You can run the program at http://programmingpraxis.codepad.org/Ea9JNyI9.

Pages: 1 2

### 2 Responses to “Subset Sum, Meet In The Middle”

1. Mike said

Kinda quiet this week.

Here’s a Python 2.7 solution:

```def subsetsum(nums, tgt):
sums = {}
for n in nums[::2]:
for k,v in sums.items() + [(0,[])]:
newsum = k + n
if newsum not in sums:
sums[newsum] = v + [n]
if newsum == tgt:
return sums[tgt]

difs = {tgt:[]}
for n in nums[1::2]:
for k,v in difs.items():
newdif = k - n
if newdif not in difs:
difs[newdif] = v + [n]
if newdif in sums:
return sums[newdif] + difs[newdif]

return []
```
2. […] ways to solve the subset sum problem. The standard solution uses dynamic programming. Another solution splits the problem space into two parts. Both solutions require exponential time, though the […]