HorowitzSahni

HorowitzSahni refers to the Horowitz–Sahni algorithm, a classic meet-in-the-middle method for solving the subset sum problem, named after its developers. Introduced in the 1970s, it provides one of the earliest and most influential applications of the meet-in-the-middle paradigm to combinatorial problems.

The method works as follows: given a set of n integers and a target sum T, the input is split into two halves. All 2^{n/2} subset sums of the first half are generated, producing a list A, while all 2^{n/2} subset sums of the second half are generated, producing a list B. The algorithm then sorts one of the lists and, for each value in the other list, searches for a complementary value that yields T when added. If such a pair exists, there is a subset whose sum equals T.

Complexity and variants: the core steps require generating two lists of size 2^{n/2}, giving a memory requirement on the order of 2^{n/2}. Sorting and searching yield a time complexity around O(2^{n/2} log 2^{n/2}), though variants using hash tables can reduce constant factors and approach closer to linearithmic performance. The algorithm is primarily used for exact decision problems (whether a subset sums to T) and can be extended to counting or enumerating subsets that achieve T, within practical limits.

Applications and significance: Horowitz–Sahni is a foundational example of the power of meet-in-the-middle strategies in algorithm design. It is often taught as a benchmark for exact subset sum solutions and influences subsequent MITM techniques in optimization and cryptography. Limitations include exponential growth with respect to n and substantial memory usage, restricting its practicality to moderate input sizes.