Subset sum problem
Decision problem in computer science / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Subset sum problem?
Summarize this article for a 10 year old
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely .[1] The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:[1]
- The variant in which all inputs are positive.
- The variant in which inputs may be positive or negative, and . For example, given the set , the answer is yes because the subset sums to zero.
- The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., . This special case of SSP is known as the partition problem.
SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.
SSP is a special case of the knapsack problem and of the multiple subset sum problem.