Editing Subset sum problem (section)

=== 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" />