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:
“Never is a historic deed already completed when it is done but always only when it is handed down to posterity. What we call “history” by no means represents the sum total of all significant deeds.... World history ... only comprises that tiny lighted sector which chanced to be placed in the spotlight by poetic or scholarly depictions.”
—Stefan Zweig (18811942)
“... your problem is your role models were models.”
—Jane Wagner (b. 1935)