and all sums xi + y for all y in L. sort Ui in ascending order make L empty let y be the smallest element of Ui add y to L for each element z of Ui in increasing order do // Trim the list by eliminating numbers close to one another // and throw out elements greater than the target sum T. if y + ε T/n < z ≤ T then y = z add z to L return the largest element in L. Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all subsets of inputs. The trimming step does two things: It ensures that all sums remaining in L are below T, so they are feasible solutions to the subset-sum problem. It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least . These properties together guarantee that the list contains no more than elements; therefore the run-time is polynomial in . 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 , so steps together introduce an error of at most . Therefore, the returned solution is at least which is at least . 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 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 (i.e., exponential in ). Kellerer, Mansini, Pferschy and Speranza and Kellerer, Pferschy and Pisinger present other FPTAS-s for subset sum. See also Knapsack problem - a generalization of SSP in which each input item has both a value and a weight. The goal is to maximize the value such that the total weight is bounded. Multiple subset sum problem - a generalization off SSP in which one should choose several subsets. 3SUM Merkle–Hellman knapsack cryptosystem References Further reading A3.2: SP13, pg.223. Weakly NP-complete problems Dynamic programming Articles with example pseudocode