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))) =>
                        (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


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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: