Subset sum problem
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset formula_1 of integers and a target-sum formula_2, and the question is to decide whether any subset of the integers sum to precisely formula_2"." The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example: 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. Computational hardness. The run-time complexity of SSP depends on two parameters: As both "n" and "L" grow large, SSP is NP-hard. The complexity of the best known algorithms is exponential in the smaller of the two parameters "n" and "L". The problem is NP-hard even when all input integers are positive (and the target-sum "T" is a part of the input). This can be proved by a  direct reduction from 3SAT. It can also be proved by reduction from 3-dimensional matching (3DM): The following variants are also known to be NP-hard: Exponential time algorithms. There are several ways to solve SSP in time exponential in "n". Inclusion–exclusion. The most naïve algorithm would be to cycle through all subsets of "n" numbers and, for every one of them, check if the subset sums to the right number. The running time is of order formula_8, since there are formula_9 subsets and, to check each subset, we need to sum at most "n" elements. The algorithm can  be implemented by depth-first search of a binary tree: each level in the tree corresponds to an input number; the left branch corresponds to excluding the number from the set, and the right branch corresponds to including the number (hence the name Inclusion-Exclusion). The memory required is formula_10. The run-time can be improved by several heuristics: Horowitz and Sahni. In 1974, Horowitz and Sahni published a faster exponential-time algorithm, which runs in time formula_11, but requires much more space - formula_12. The algorithm splits arbitrarily the "n" elements into two sets of formula_13 each. For each of  these two sets, it stores a list of the sums of all formula_14 possible subsets of its elements. Each of these two lists is then sorted. Using even the fastest comparison sorting algorithm, Mergesort for this step would take time formula_15. However, given a sorted list of sums for formula_16 elements, the list can be expanded to two sorted lists with the introduction of a (formula_17)th element, and these two sorted lists can be merged in time formula_18. Thus, each list can be generated in sorted form in time formula_19. Given the two sorted lists, the algorithm can check if  an element of the first array and an element of the second array sum up to "T" in time formula_19. To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than "T", the algorithm moves to the next element in the first array. If it is less than "T", the algorithm moves to the next element in the second  array. If two elements that sum to "T" are found, it stops. Schroeppel and Shamir. Schroeppel and Shamir presented an algorithm based on Horowitz and Sanhi, that requires similar runtime - formula_21, much less space - formula_22. Rather than generating and storing all subsets of "n"/2 elements in advance, they partition the elements into 4 sets of "n"/4 elements each, and generate subsets of "n"/2 element pairs dynamically using a min heap which yields the above time and space complexities since this can be done in formula_23 and space formula_24 given 4 lists of length k. Due to space requirements, the HS  algorithm is practical for up to about 50 integers, and the SS algorithm is practical for up to 100 integers. Howgrave-Graham and Joux. Howgrave-Graham and Joux presented a probabilistic algorithm that runs faster than all previous ones - in time formula_25 using space formula_26. It solves only the decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to "T". The techniques of Howgrave-Graham and Joux were subsequently extended bringing the time-complexity to formula_27. Pseudo-polynomial time dynamic programming solutions. SSP can be solved in pseudo -polynomial time using dynamic programming. Suppose we have the following sequence of elements in an instance: We define a "state" as a pair ("i", "s") of integers. This state represents the fact that Each state ("i", "s") has two next states: Starting from the initial state (0, 0), it is possible to use any graph search algorithm (e.g. BFS) to search the state ("N", "T"). If the state is found, then by backtracking we can find a subset with a sum of exactly "T". The run-time of this algorithm is at most linear in the number of states. The  number of states is at most "N" times the number of different possible sums. Let be the sum of the negative values and the sum of the positive values; the number of different possible sums is at most "B"-"A", so the total runtime is in formula_33. For example, if all input values are positive and bounded by some constant "C", then "B" is at most "N C", so the time required is formula_34. This solution does not count as polynomial time in complexity theory because formula_35 is not polynomial in the "size" of the problem, which is the number of  bits used to represent it. This algorithm is polynomial in the values of and , which are exponential in their numbers of bits. However, Subset Sum encoded in "unary" is in P, since then the size of the encoding is linear in B-A. Hence, Subset Sum is only "weakly" NP-Complete. For the case that each formula_36 is positive and bounded by a fixed constant , Pisinger found a linear time algorithm having time complexity formula_37 (note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial). In  2015, Koiliaris and Xu found a deterministic formula_38 algorithm for the subset sum problem where is the sum we need to find. In 2017, Bringmann found a randomized formula_39 time algorithm. In 2014, Curtis and Sanches found a simple recursion highly scalable in SIMD machines having formula_40 time and formula_41 space, where is the number of processing elements, formula_42 and formula_43 is the lowest integer. This is the best theoretical parallel complexity known so far. A comparison of practical results and the solution of hard instances of the SSP is discussed by Curtis and Sanches. Polynomial time approximation algorithms. Suppose  all inputs are positive. An approximation algorithm to SSP aims to find a subset of "S" with a sum of at most "T" and at least "r" times the optimal sum, where "r" is a number in (0,1) called the "approximation ratio". Simple 1/2-approximation. The following very simple algorithm has an approximation ratio of 1/2: When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset, so it must be smaller  than "T"/2. Therefore, the sum of inputs in the subset is more than "T"/2, which is obviously more than OPT/2. Fully-polynomial time approximation scheme. The following algorithm attains, for every formula_44, an approximation ratio of formula_45. Its run time is polynomial in and formula_46. Recall that "n" is the number of inputs and "T" is the upper bound to the subset sum. Note that without the trimming step (the inner "for each" loop), the list "L" would contain the sums of all formula_9 subsets of inputs. The trimming step does two things: These properties together guarantee that the list  contains no more than formula_49 elements; therefore the run-time is polynomial in formula_49. When the algorithm ends, if the optimal sum is in , then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step. Each trimming step introduces an additive error of at most formula_48, so steps together introduce an error of at most formula_52. Therefore, the returned solution is at least formula_53 which is at least formula_54 . The above algorithm provides an "exact" solution to SSP in the case that the input numbers are small (and non-negative). If any  sum of the numbers can be specified with at most bits, then solving the problem approximately with formula_55 is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in and formula_56 (i.e., exponential in ). Kellerer, Mansini, Pferschy and Speranza and Kellerer, Pferschy and Pisinger present other FPTAS-s for subset sum.