The subset-sum problem discussed in this paper is as follows: Given a set A of m distinct integers in the interval [ 1 , l ] and an integer N, find a subset B ⊆ A such that S _B ≤ N and no set C ⊆ A exists with S _B < S _c ≤ N. Here S _B denotes the sum of B’s elements. Although the problem is known to be NP-hard, a pseudopolynomial dynamic program exists that solves it. So too does an algorithm, derived using analytic number theoretic methods, for the restricted case of dense A. The algorithm introduced in this paper, also concerned with the dense case, is not only an improvement over the previous algorithm’s performance (and the dynamic program’s as well), but is proven using elementary number theory.

The authors first provide an outline of the algorithm and later fill in the details. En route, they characterize the set of all subset sums of A. The earlier analytic number theoretic approach also did this. Because only elementary number theory is used in this paper, however, it is more widely accessible. The intended audience is readers interested in the analysis of computer algorithms, especially the subset-sum problem. For that group in particular, the authors note that this paper nicely complements Lagarias and Odlyzko’s [1], which treats the case of sparse A. The bibliography is good, but the paper includes an apparently erroneous reference to pages 201–206 in Aho et al. [2] for the fast Fourier transform.