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:
“If the twentieth century is to be better than the nineteenth, it will be because there are among us men who walk in Priestley’s footsteps....To all eternity, the sum of truth and right will have been increased by their means; to all eternity, falsehoods and injustice will be the weaker because they have lived.”
—Thomas Henry Huxley (1825–95)
“Consciousness is what makes the mind-body problem really intractable.”
—Thomas Nagel (b. 1938)