Subset Sum, Meet In The Middle

March 30, 2012

We looked at the brute-force algorithm for the subset sum problem in the previous exercise. Today we look at a different algorithm that solves the same problem; the new algorithm is more efficient, but still exponential, with a time complexity of 0(n2n/2).

The new algorithm, called the meet in the middle algorithm, splits the input list into equal-size halves. The first half is subject to the same algorithm as the previous exercise, in which all subsets are generated, their sums computed, and the sums compared to the target. It is possible but unlikely that the target will be found in the first half. If not, the algorithm generates all subsets of the second half and checks each sum to see if the difference between target and sum was a sum in the first half, in which case the required subset has been found.

Your task is to implement the meet in the middle algorithm for solving 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.

About these ads

Pages: 1 2

One Response 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 []
    

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: