Editing Subset sum problem (section)

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