Subset sum problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The subset sum problem is an important problem of computer science. It can be stated as follows: Given a set of integers, does any subset of them sum to 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. It can be reformulated to the 3SAT. An alternative statement of this problem is, given a set of numbers and an integer x determine whether or not there exist a subset that sums up to x. Eg. given a set {1, 4, 6, 7} and x = 10 the answer is yes because {4, 6} sums to 10. Remember that the subsequence need not to be contiguous. For instance if x = 8 in above example the answer is still yes because {1, 7} sums to 8.