  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_i x_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|<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_{i} 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.
