World's most popular travel blog for travel bloggers.

# Subset Sum algorithm, why not split by 3+?

, ,
Problem Detail:

A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of combinations by comparing the highest and lowest sums from each A and B.

Do we know (or does someone have an argument) why not to split the input into 3 or more sets rather than two?

I presume that there would be a combinatorial proof that doing so would either require the same or more number of steps.

###### Answered By : Yuval Filmus

First of all, let me mention that the algorithm you mention is attributed to Horowitz and Sahni (1974), whose algorithm achieves time $O(2^{n/2})$ and space $O(2^{n/2})$. A major improvement due to Schroeppel and Shamir (1981) reduces memory consumption to $O(2^{n/4})$ while keeping the same running time; this algorithm divides the input into four sets.

The topic is of interest to cryptographers, and there has been a recent line of improvements: Howgrave-Graham and Joux (2010), Becker, Coron and Joux (2011), Dinur, Dunkelman, Keller and Shamir (2012) and Austrin, Kaski, Koivisto and Määttä (2013), which seems to be the latest word on the subject; the authors of the last paper are actually not cryptographers.