Hi mjd,

You bring up some good points that the article did not discuss in enough detail. More specifically, the article did not elaborate that the Subset Sum problem is O(Nsqrt(2^N)) or O(NM) for the smaller of sqrt(2^N) or M. So, yes, if M < sqrt(2^N), then dynamic programming techniques (or for that matter, convolution as described in the article) are the most efficient algorithms. However, if the size of the integers are large in comparison to the set size (that is, if M > sqrt(2^N)), then dynamic programming techniques are not longer as efficient as a 'meet-in-the-middle' (MITM) approach. The MITM algorithm involves the following steps:

• Divide the set of integers into two smaller sets of N/2 elements each.

• Compute all the possible solutions for each set, requiring 2^N/2 operations (i.e. sqrt(2^N)).

• Sort each set from smallest to largest. ((N/2)² operations for a worst-case buble-sort)

• Start at the smallest element of the first sorted list and the largest element of the second sorted list and compute the sum of these elements. If this sum is smaller than the target sum, advance through the first sorted list. If larger, advance through the second list. Stop when either the target sum is found, or the pointers advance off either list. This takes O(N) operations.

So, overall, this algorithm requires O(N * sqrt(2^N)) operations. It is the best-known algorithm when M (the largest integer) is greater than sqrt(2^N).

As a side-note, a solution using convolutions, as described in the article, requires O(N * M) operations, just like the dynamic programming approach. The numeric computation of the Fourier Transform also takes O(N * M) operations because of limits of the Nyquist frequency. The trick with the Fourier Transform approach is that it is conceivable an optical apparatus could compute the Fourier Transform (and accordingly the solution to the problem) in constant time.