Given a set of n input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time $O*(3^{0.387n})$ in the average case, significantly improving over the $O*(3^{0.488n})$ running time of the best known worst-case algorithm and the Meet-in-the-Middle benchmark of $O*(3^{0.5n}).$
Our algorithm generalizes to a number of related problems, such as the ``Generalized Equal Subset Sum'' problem, which asks us to assign a coefficient $c_i$ from a set $C$ to each input number $x_i$ such that $\sum_i c_ix_i = 0$. Our algorithm for the average-case version of this problem runs in time $|C|^{(0.5-c_0/|C|)}n$ for some positive constant $c_0$, whenever $C=\{0,\pm 1,\dots ,\pm d\}$ or $\{\pm 1, \dots, \pm d\}$ for some positive integer $d$ (with $O*(|C|^{0.45n})$ when $|C|$ is less than 10). Our results extend to the problem of finding ``nearly balanced'' solutions in which the target is a not-too-large nonzero offset $\tau$.
Our approach relies on new structural results that characterize the probability that $\sum_u c_i x_i = \tau$ has a solution $c \in C_n$ when $x_i$'s are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the ``representation technique'' introduced by Howgrave-Graham and Joux. This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.