Wikipedia describes an algorithm for the subset sum problem which runs in time $O(2^{\frac{n}{2}})$. It works by dividing the set in half once, computing all the sums in each half (cleverly presorted), negating each element in the set of sums for one of the halves, and then checking if the intersection exists, in which case there is a subset summing to $0$.

I wonder if there is a recursive version of this algorithm? The running time suggests that there could be some way of recursing on two subsets of $n - 2$ elements and performing some constant-time computation. Are there any interesting ways this algorithm can be restated recursively or otherwise?

  • $\begingroup$ The WP page describesa recursive method for creating the presorted lists where doubling the list length by introducing a new element is done with a single pass. $\endgroup$ Aug 20 '13 at 6:11
  • $\begingroup$ I understand that part but I mean for the algorithm as a whole to be stated recursively somehow. For example the naive $O(2^n)$ algorithm can be stated recursively, let $x \in S$ and $S' = S \setminus \{x\}$ and we can check if $S'$ has a subset summing to $0$ or if $S'$ has a subset summing to $-x$. $\endgroup$ Aug 20 '13 at 6:17
  • $\begingroup$ Any program (Turing machine) can be translated into a recursive version (lambda term), but I doubt this is what you want... $\endgroup$
    – dtldarek
    Aug 20 '13 at 7:14

There has been a recent series of papers improving the exponential subset algorithms (at least in the average case).

The first two paper work on a classical computer with complexity close to $2^{n/3}$, the third one on a quantum computer with complexity close to $2^{n/4}.$

Apparently the key idea is to decompose the subset sum in two halves in a less constrained way. These algorithms also use a limited form of recursivity (only a few levels).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.