In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set { −7, −3, −2, 5, 8}, the answer is yes because the subset { −3, −2, 5} sums to zero. The problem is NP-complete.
An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.
Read more about Subset Sum Problem: Complexity, Exponential Time Algorithm, Pseudo-polynomial Time Dynamic Programming Solution, Polynomial Time Approximate Algorithm, Further Reading
Famous quotes containing the words sum and/or problem:
“To sum up our most serious objections in a few words, we should say that Carlyle indicates a depth—and we mean not impliedly, but distinctly—which he neglects to fathom.”
—Henry David Thoreau (1817–1862)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)