Editing Subset sum problem (section)

== Exponential time algorithms ==

There are several ways to solve SSP in time exponential in ''n''.<ref name=":0">{{Cite web|first1=Richard E.|last1= Korf|author1-link=Richard E. Korf|first2= Ethan L. |last2=Schreiber|first3=Michael D.|last3=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>.