Lesson plan

subset sum problem

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T , and the question is to decide whether any subset of the integers sum to precisely T . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: * The variant in which all inputs are positive. * The variant in which inputs may be positive or negative, and T=0 . For example, given the set \{-7, -3, -2, 9000, 5, 8\} , the answer is yes because the subset \{-3, -2, 5\} 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., T = \frac{1}{2}(a_1+\dots+a_n) . 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.

Back to article

Article summary

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T , and the question is to decide whether any subset of the integers sum to precisely T . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: * The variant in which all inputs are positive. * The variant in which inputs may be positive or negative, and T=0 . For example, given the set \{-7, -3, -2, 9000, 5, 8\} , the answer is yes because the subset \{-3, -2, 5\} 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., T = \frac{1}{2}(a_1+\dots+a_n) . 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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.