# Algorithm of the Week: Finding Sum-Free Subsets

Join the DZone community and get the full member experience.

Join For FreeA set of integers is called sum-free if no element of the set is the sum of any other pair of elements in the set. For example, {1, 10, 100} is sum-free.

Let’s look at pulling out a sum-free subset of a larger set. For example, if we start with {1, 2, 3, …, 10}, then {1, 5, 10} as a sum-free subset. So is {1, 2, 4, 7}. Notice in this case 1 + 2 + 4 = 7, but that’s OK because we’re only concerned with whether an element is the sum of two other elements.

Now let *A* be a set of integers with *n* elements. How large of a sum-free subset does *A* contain? It could be as large as *n* if the set *A* were sum-free to begin with, so that’s an upper bound. But what is a lower bound on the size of the largest sum-free subset?

There is a theorem that gives a number *k* such that every set of *n* non-zero integers contains a sum-free subset of size at least *kn*. You could let *k* be zero, but that’s no fun. Can you find a larger value of *k*? I’ll tell you later what value of *k* the theorem has. Until then, maybe you could try to find your own value.

Suppose you want to write a program to explore this empirically. For a given set, how would you find a maximal sum-free subset? Brute force examination of all subsets would take 2^{n} steps, so hopefully you could do better than that.

What are some sets that have relatively small maximal sum-free subsets?

**Update**: Results here.

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments