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.
Programming Praxis 
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 [][…] 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 […]