A subset sum of a finite set of numbers is the sum of the elements
of a subset of
. The set
of all attainable subset sums is
|
(1)
|
where the empty subset contributes 0.
For , the eight subsets
give the sums
|
(2)
| |||
|
(3)
| |||
|
(4)
| |||
|
(5)
| |||
|
(6)
| |||
|
(7)
| |||
|
(8)
| |||
|
(9)
|
so the sum appearing most often is 3, which occurs twice, and has seven elements. More generally, for
with
a nonnegative integer,
every integer from 0 through
is attainable, so
|
(10)
|
For , 2, ..., the numbers of distinct subset sums are
2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (OEIS A000124).
When consists of nonnegative
integers, the coefficient of
in
counts the subsets with sum
.
Thus,
is the set
of exponents with nonzero coefficients. The definition also applies to subsets
of finite abelian groups, where bounds on
are studied in additive combinatorics (Griffiths
2009).
The term "subset sum" is also used as a short name for the subset sum problem, which asks questions about attainable sums.
For subsets of finite Abelian groups, zero-sum-free sets have many distinct nonempty subset sums. Liu (2026)
proved the lower bound for a zero-sum-free set of
distinct elements. It gives a
logarithmic error term in the upper bound for the
Olson constant.
An extremal avoidance question is the Erdős-Graham subset sum problem, which maximizes the size of a subset
of avoiding the target sum
. The floor notation denotes the floor
function. Unlike the algorithmic subset sum
problem, its input is the interval and target rather than a supplied set.