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:
“The ornament is a statuette, a black figure of a bird. I am prepared to pay on behalf of the figure’s rightful owner the sum of $5000 for its recovery. I am prepared to promise, to promise ... what is the phrase?—’No questions will be asked.’”
—John Huston (1906–1987)
“Our political problem now is “Can we, as a nation, continue together permanentlyforever—half slave, and half free?” The problem is too mighty for me. May God, in his mercy, superintend the solution.”
—Abraham Lincoln (1809–1865)