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 die proudly when it is no longer possible to live proudly. Death freely chosen, death at the right time, brightly and cheerfully accomplished amid children and witnesses: then a real farewell is still possible, as the one who is taking leave is still there; also a real estimate of what one has wished, drawing the sum of one’s life—all in opposition to the wretched and revolting comedy that Christianity has made of the hour of death.”
—Friedrich Nietzsche (1844–1900)
“The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
—Lawrence Kutner (20th century)