View source for Subset sum problem

{{Short description|Decision problem in computer science}}
The '''subset sum problem''' (SSP) is a [[decision problem]] in [[computer science]]. In its most general formulation, there is a [[multiset]] <math>S</math> of integers and a target-sum <math>T</math>, and the question is to decide whether any subset of the integers sum to precisely <math>T</math>''.''<ref name="kleinberg2006p491">{{cite book|last1=Kleinberg|first1=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=Algorithm Design|last2=Tardos|first2=Éva|year=2006|isbn=0-321-37291-3|edition=2nd|page=[https://archive.org/details/algorithmdesign0000klei/page/491 491]|url-access=registration}}</ref> The problem is known to be [[NP-completeness|NP-complete]]. Moreover, some restricted variants of it are NP-complete too, for example:<ref name="kleinberg2006p491" />

* The variant in which all inputs are positive.
* The variant in which inputs may be positive or negative, and <math>T=0</math>. For example, given the set <math>\{-7, -3, -2, 9000, 5, 8\}</math>, the answer is ''yes'' because the subset <math>\{-3, -2, 5\}</math> 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., <math> T = \frac{1}{2}(a_1+\dots+a_n)</math> .  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.

== Computational hardness ==

The [[run-time complexity]] of SSP depends on two parameters: 

* {{nobold|''n''}} - the number of input integers. If ''n'' is a small fixed number, then an [[exhaustive search]] for the solution is practical.
* {{nobold|''L''}} - the precision of the problem, stated as the number of binary place values that it takes to state the problem. If ''L'' is a small fixed number, then there are [[dynamic programming]] algorithms that can solve it exactly.

As both ''n'' and ''L'' grow large, SSP is NP-hard. The complexity of the best known algorithms is [[Exponential time|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]].<ref>{{Cite web |last=Goodrich |first=Michael |title=More NP complete and NP hard problems |url=https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-date=2022-10-09 |url-status=live}}</ref> It can also be proved by reduction from [[3-dimensional matching]] (3DM):<ref name="garey79">{{Garey-Johnson}}, Section&nbsp;3.1 and problem&nbsp;SP1 in Appendix&nbsp;A.3.1.</ref>

* We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has ''n'' vertices. There are ''m'' edges, where each edge contains exactly one vertex from each of W, X, Y.  Denote ''L'' := ceiling(log<sub>2</sub>(''m''+1)), so that ''L'' is larger than the number of bits required to represent the number of edges.
* We construct an instance of SSP with ''m'' positive integers. The integers are described by their binary representation. Each input integer can be represented by 3''nL'' bits, divided into 3''n'' zones of ''L'' bits. Each zone corresponds to a vertex.
* For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least-significant bits in the zones of the vertices w, x, and y. For example, if ''n''=10 and L=3, and W=(0,...,9), X=(10,...,19), Y=(20,...,29), then the edge (0, 10, 20) is represented by the number (2<sup>0</sup>+2<sup>30</sup>+2<sup>60</sup>).
* The target sum ''T'' in the SSP instance is set to an integer with "1" in the least-significant bit of every zone, that is, (2<sup>0</sup>+2<sup>1</sup>+...+2<sup>3n-1</sup>).
* If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T.
* Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance.

The following variants are also known to be NP-hard:

* The input integers can be both positive and negative, and the target-sum ''T'' = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero.  Given an instance (''S'', ''T'') of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value &minus;''T''.  Given a solution to the SubsetSumPositive instance, adding the &minus;''T'' yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the &minus;''T'' (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +''T'', which is a solution of the SubsetSumPositive instance.
*The input integers are positive, and ''T'' = sum(''S'')/2. This can also be proved by reduction from the general variant; see [[partition problem]].

The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is [[Sharp P complete|#P-complete]].<ref>[[Yuval Filmus|Filmus, Yuval]] (30 January 2016).  [https://cs.stackexchange.com/a/52466 Answer] to: "[https://cs.stackexchange.com/q/52453 Is there a known, fast algorithm for counting all subsets that sum to below a certain number?]".  ''Theoretical Computer Science [[Stack Exchange]].''  Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison".  ''Theoretical Computer Science''.  Elsevier.  '''410''': 101-107.  DOI&nbsp;[http://dx.doi.org/10.1016/j.tcs.2008.09.034 10.1016/j.tcs.2008.09.034]) does not in fact prove the claim, instead directing readers to another citation ([[Christos Papadimitriou|Papadimitriou, Christos]] (1994). [https://archive.org/details/computationalcom0000papa/ ''Computational Complexity''].  Addison-Wesley: Reading, MA.  Chapter&nbsp;9.  {{ISBN|0-201-53082-1}}&nbsp;&mdash; via the [[Internet Archive]]), which does not explicitly prove the claim either.  Papadimitriou's proof that SSP is NP-complete via reduction of [[3SAT]] does, however, generalize to a reduction from [[Sharp-SAT|#3SAT]] to #SSP.</ref>

== Exponential time algorithms ==

There are several ways to solve SSP in time exponential in ''n''.<ref name=":0">{{Cite web|last=Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt|date=2014|title=Optimal Sequential Multi-Way Number Partitioning|url=https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

=== Inclusion–exclusion ===
The most [[naive solution|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 <math>O(2^n \cdot n)</math>, since there are <math>2^n</math> 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 <math>O(n)</math>. The run-time can be improved by several heuristics:<ref name=":0" />

* Process the input numbers in descending order.
* If the integers included in a given node exceed the sum of the best subset found so far, the node is pruned.
* If the integers included in a given node, plus all remaining integers, are less than the sum of the best subset found so far, the node is pruned.

=== Horowitz and Sahni ===
In 1974, Horowitz and [[Sartaj Sahni|Sahni]]<ref>{{cite journal|last1=Horowitz|first1=Ellis|title=Computing partitions with applications to the knapsack problem|url=https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-date=2022-10-09 |url-status=live|journal=[[Journal of the Association for Computing Machinery]]|volume=21|issue=2|pages=277–292|year=1974|doi=10.1145/321812.321823|mr=0354006|last2=Sahni|first2=Sartaj|author2-link=Sartaj Sahni|hdl=1813/5989|s2cid=16866858|hdl-access=free}}</ref> published a faster exponential-time algorithm, which runs in time <math>O( 2^{n/2}\cdot (n/2))</math>, but requires much more space - <math>O( 2^{n/2})</math>. The algorithm splits arbitrarily the ''n'' elements into two sets of <math>n/2</math> each. For each of these two sets, it stores a list of the sums of all <math>2^{n/2}</math> 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 <math>O(2^{n/2}n)</math>.  However, given a sorted list of sums for <math>k</math> elements, the list can be expanded to two sorted lists with the introduction of a (<math>k+1</math>)th element, and these two sorted lists can be merged in time <math>O(2^k)</math>.  Thus, each list can be generated in sorted form in time <math>O(2^{n/2})</math>.  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 <math>O(2^{n/2})</math>. 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. (The sub-problem for two elements sum is known as two-sum.<ref>{{Cite web |title=The Two-Sum Problem |url=https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-date=2022-10-09 |url-status=live}}</ref>)

=== Schroeppel and Shamir ===
In 1981, [[Richard Schroeppel|Schroeppel]] and [[Adi Shamir|Shamir]] presented an algorithm<ref>{{Cite journal|last1=Schroeppel|first1=Richard|last2=Shamir|first2=Adi|date=1981-08-01|title=A {{math|''T'' {{=}} ''O''(2<sup>''n''/2</sup>)}}, {{math|''S'' {{=}} ''O''(2<sup>''n''/4</sup>)}} algorithm for certain NP-complete problems|url=https://epubs.siam.org/doi/abs/10.1137/0210033|journal=SIAM Journal on Computing|volume=10|issue=3|pages=456–464|doi=10.1137/0210033|issn=0097-5397}}</ref> based on Horowitz and Sanhi, that requires similar runtime - <math>O( 2^{n/2}\cdot (n/4))</math>, much less space - <math>O(2^{n/4})</math>. 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 <math>O(k^{2}\log(k))</math> and space <math>O(k)</math> 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.<ref name=":0" />

=== Howgrave-Graham and Joux ===
In 2010, Howgrave-Graham and Joux<ref>{{Cite book|last1=Howgrave-Graham|first1=Nick|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2010 |chapter=New Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6110|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=235–256|doi=10.1007/978-3-642-13190-5_12|isbn=978-3-642-13190-5|doi-access=free}}</ref> presented a [[probabilistic algorithm]] that runs faster than all previous ones - in time <math>O(2^{0.337n})</math> using space <math>O(2^{0.256n})</math>. 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<ref>{{Cite book|last1=Becker|first1=Anja|last2=Coron|first2=Jean-Sébastien|last3=Joux|first3=Antoine|title=Advances in Cryptology – EUROCRYPT 2011 |chapter=Improved Generic Algorithms for Hard Knapsacks |date=2011|editor-last=Patterson|editor-first=Kenneth|series=Lecture Notes in Computer Science|volume=6632|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=364–385|doi=10.1007/978-3-642-20465-4_21|isbn=978-3-642-20465-4|doi-access=free}}</ref> bringing the time complexity to <math>O(2^{0.291n})</math>. A more recent generalization<ref>{{Cite book|last1=Bonnetain|first1=Xavier|last2=Bricout|first2=Rémi|last3=Schrottenloher|first3=André|last4=Shen|first4=Yixin|title=Advances in Cryptology - ASIACRYPT 2020 |chapter=Improved Classical and Quantum Algorithms for Subset-Sum |date=2020|editor-last1=Moriai|editor-first1=Shiho|editor-last2=Wang|editor-first2=Huaxiong|series=Lecture Notes in Computer Science|volume=12492|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=633-666|doi=10.1007/978-3-030-64834-3_22|isbn=978-3-030-64833-6|doi-access=free}}</ref> lowered the time complexity to <math>O(2^{0.283n})</math>.

== 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:

:<math>x_1,\ldots, x_N</math>

We define a ''state'' as a pair (''i'', ''s'') of integers. This state represents the fact that

:"there is a nonempty subset of <math>x_1,\ldots, x_i</math> which sums to {{mvar|s}}."

Each state (''i'', ''s'') has two next states:

* (''i''+1, ''s''), implying that <math>x_{i+1}</math> is not included in the subset;
* (''i''+1, ''s''+<math>x_{i+1}</math>), implying that <math>x_{i+1}</math> is included in the subset.

Starting from the initial state (0, 0), it is possible to use any graph search algorithm (e.g. [[Breadth-first search|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 {{mvar|A}} be the sum of the negative values and {{mvar|B}} the sum of the positive values; the number of different possible sums is at most ''B''-''A'', so the total runtime is in <math>O(N(B-A))</math>. 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 <math>O(N^{2}C)</math>.

This solution does not count as polynomial time in complexity theory because <math>B-A</math> 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 {{mvar|A}} and {{mvar|B}}, 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 <math>x_i</math> is positive and bounded by a fixed constant {{mvar|C}}, in 1999, Pisinger found a linear time algorithm having time complexity <math>O(NC)</math> (note that this is for the version of the problem where the target sum is not necessarily zero, as otherwise the problem would be trivial).<ref name="Pisinger09">{{cite journal | last = Pisinger | first = David | doi = 10.1006/jagm.1999.1034 | issue = 1 | journal = Journal of Algorithms | mr = 1712690 | pages = 1–14 | title = Linear time algorithms for knapsack problems with bounded weights | volume = 33 | year = 1999}}</ref> In 2015, Koiliaris and Xu found a deterministic <math>\tilde{O}(T \sqrt N)</math> algorithm for the subset sum problem where {{mvar|T}} is the sum we need to find.<ref>{{Cite arXiv|title = A Faster Pseudopolynomial Time Algorithm for Subset Sum |eprint = 1507.02318 |date = 2015-07-08|first1 = Konstantinos|last1 = Koiliaris|first2 = Chao|last2 = Xu|class = cs.DS }}</ref> In 2017, Bringmann found a randomized <math>\tilde{O}(T+N)</math> time algorithm.<ref>{{cite conference | last = Bringmann | first = Karl | editor-last = Klein | editor-first = Philip N. | arxiv = 1610.04712 | contribution = A near-linear pseudopolynomial time algorithm for subset sum | doi = 10.1137/1.9781611974782.69 | pages = 1073–1084 | publisher = SIAM | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | year = 2017}}</ref>

In 2014, Curtis and Sanches found a simple recursion highly scalable in [[SIMD]] machines having <math>O(N(m-x_{\min})/p)</math> time and <math>O(N+m-x_{\min})</math> space, where {{mvar|p}} is the number of processing elements, <math>m=\min(s, \sum x_i - s)</math> and <math>x_{\min}</math> is the lowest integer.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU |journal=Concurrency and Computation: Practice and Experience |date=January 2016 |volume=28 |issue=1 |pages=95–113 |doi=10.1002/cpe.3636|s2cid=20927927 }}</ref> 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.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=A low-space algorithm for the subset-sum problem on GPU |journal=Computers & Operations Research |date=July 2017 |volume=83 |pages=120–124 |doi=10.1016/j.cor.2017.02.006}}</ref>

== Polynomial time approximation algorithms ==

{{More citations needed section|date=February 2021}}

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:<ref name=":1">{{Cite journal|last1=Caprara|first1=Alberto|last2=Kellerer|first2=Hans|last3=Pferschy|first3=Ulrich|date=2000-02-01|title=The Multiple Subset Sum Problem|url=https://doi.org/10.1137/S1052623498348481|journal=SIAM Journal on Optimization|volume=11|issue=2|pages=308–319|doi=10.1137/S1052623498348481|issn=1052-6234}}</ref>

* Order the inputs by descending value;
* Put the next-largest input into the subset, as long as it fits there.

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 and the sum of inputs in the subset is more than ''T''/2 otherwise the input also is less than T/2 and it would fit in the set. Such a sum greater than T/2  is obviously more than OPT/2.

=== Fully-polynomial time approximation scheme{{Anchor|FPTAS}} ===
The following algorithm attains, for every <math>\epsilon>0</math>, an approximation ratio of <math>(1-\epsilon)</math>. Its run time is polynomial in {{mvar|n}} and <math>1/\epsilon</math>. Recall that ''n'' is the number of inputs and ''T'' is the upper bound to the subset sum.
 initialize a list ''L'' to contain one element 0.
 
 '''for each''' ''i'' from 1 to ''n'' '''do'''
     let ''U<sub>i</sub>'' be a list containing all elements ''y'' in ''L'', and all sums ''x<sub>i</sub>'' + ''y'' for all ''y'' in ''L''.
     sort ''U<sub>i</sub>'' in ascending order
     make ''L'' empty 
     let ''y'' be the smallest element of ''U<sub>i</sub>''
     add ''y'' to ''L''
     '''for each''' element ''z'' of ''U<sub>i</sub>'' in increasing order '''do'''
         <u>// Trim the list by eliminating numbers close to one another</u>
         <u>// and throw out elements greater than the target sum ''T''.</u>
         '''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 <math>2^n</math> 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 <math>\epsilon T/n</math>. 

These properties together guarantee that the list {{mvar|L}} contains no more than <math>n/\epsilon</math> elements; therefore the run-time is polynomial in <math>n/\epsilon</math>.

When the algorithm ends, if the optimal sum is in {{mvar|L}}, 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 <math>\epsilon T/n</math>,  so {{mvar|n}} steps together introduce an error of at most <math>\epsilon T</math>. Therefore, the returned solution is at least <math>\text{OPT}-\epsilon T</math> which is at least <math>(1-\epsilon)\text{OPT}</math> .

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 {{mvar|P}} bits, then solving the problem approximately with <math>\epsilon = 2^{-P}</math> is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in {{mvar|n}} and <math>2^P</math> (i.e., exponential in {{mvar|P}}).

Kellerer, Mansini, Pferschy and Speranza<ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Mansini|first2=Renata|last3=Pferschy|first3=Ulrich|last4=Speranza|first4=Maria Grazia|date=2003-03-01|title=An efficient fully polynomial approximation scheme for the Subset-Sum Problem|journal=Journal of Computer and System Sciences|language=en|volume=66|issue=2|pages=349–370|doi=10.1016/S0022-0000(03)00006-0|issn=0022-0000|doi-access=}}</ref> and Kellerer, Pferschy and Pisinger<ref name="knapsack">{{cite book|author1=Hans Kellerer|title=Knapsack problems|url=https://books.google.com/books?id=u5DB7gck08YC&pg=PA97|page=97|year=2004|publisher=Springer|isbn=9783540402862|author2=Ulrich Pferschy|author3=David Pisinger}}</ref> present other FPTASes for subset sum.

== See also ==
* {{annotated link|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'' subject to a bound on the total ''weight''.
*{{annotated link|Multiple subset sum problem}} - a generalization of SSP in which one should choose several subsets.
*{{annotated link|3SUM}}
* {{annotated link|Merkle–Hellman knapsack cryptosystem}}

== References ==
{{reflist}}

==Further reading==
* {{Introduction to Algorithms|2|chapter=35.5: The subset-sum problem}}
* {{cite book | author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5 | url-access = registration | url = https://archive.org/details/computersintract0000gare }} A3.2: SP13, pg.223.
* {{Cite journal|last1=Lagarias|first1=J. C.|last2=Odlyzko|first2=A. M.|date=1985-01-01|title=Solving low-density subset sum problems|journal=Journal of the ACM|volume=32|issue=1|pages=229–246|doi=10.1145/2455.2461|s2cid=885632|issn=0004-5411|doi-access=free}}
* {{cite book|last1=Martello|first1=Silvano|title=Knapsack problems: Algorithms and computer interpretations|last2=Toth|first2=Paolo|publisher=Wiley-Interscience|year=1990|isbn=0-471-92420-2|pages=[https://archive.org/details/knapsackproblems0000mart/page/105 105–136]|chapter=4 Subset-sum problem|mr=1086874|chapter-url=https://archive.org/details/knapsackproblems0000mart/page/105}}

{{DEFAULTSORT:Subset Sum Problem}}
[[Category:Weakly NP-complete problems]]
[[Category:Dynamic programming]]
[[Category:Articles with example pseudocode]]