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:
“And what is the potential man, after all? Is he not the sum of all that is human? Divine, in other words?”
—Henry Miller (1891–1980)
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)