# Recursive formula for subset sum?

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?

• 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. Aug 20 '13 at 6:11
• 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$. Aug 20 '13 at 6:17
• Any program (Turing machine) can be translated into a recursive version (lambda term), but I doubt this is what you want... Aug 20 '13 at 7:14

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}.$