Horowitz-Sahni algorithm in Python
Solves subset sum in O(2^(n/2)) time by sorting the sums of each half and merging them.
- File
horowitz_sahni_algorithm.py, 52 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/horowitz-sahni-algorithm/. The authors are listed in prov/7817P3.jsonl.
Entry = tuple[int, int] # (sum, bit mask of the indices)
def sorted_sums(a: list[int], lo: int, hi: int) -> list[Entry]:
"""Return (sum, mask) for each subset of the indices lo .. hi - 1 of a, sorted by sum.
Bit k of mask is set when index k is in the subset. Each new item doubles
the list by a merge, so the cost is Theta(2^(hi - lo)) time and space.
"""
s: list[Entry] = [(0, 0)] # @line L11
for k in range(lo, hi): # @line L12
bit = 1 << k
s2 = [(v + a[k], m | bit) for v, m in s] # @line L13
merged: list[Entry] = [] # @line L14
i = j = 0
while i < len(s) and j < len(s2):
if s[i][0] <= s2[j][0]:
merged.append(s[i])
i += 1
else:
merged.append(s2[j])
j += 1
merged.extend(s[i:])
merged.extend(s2[j:])
s = merged
return s # @line L15
def horowitz_sahni_algorithm(a: list[int], t: int) -> list[int] | None:
"""Return sorted 0-based indices of a subset of a with sum t, or None if there is none.
The numbers and t are any integers; the empty subset answers t == 0.
Cost: Theta(2^(n/2)) time and space for n = len(a).
"""
n = len(a)
h = n // 2 # @line L1
A = sorted_sums(a, 0, h) # @line L2
B = sorted_sums(a, h, n) # @line L3
i, j = 0, len(B) - 1 # @line L4
while i < len(A) and j >= 0: # @line L5
s = A[i][0] + B[j][0] # @line L6
if s == t: # @line L7
mask = A[i][1] | B[j][1]
return [k for k in range(n) if mask >> k & 1]
elif s < t: # @line L8
i += 1
else: # @line L9
j -= 1
return None # @line L10
test_horowitz_sahni_algorithm.py 64 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/horowitz-sahni-algorithm/. The authors are listed in prov/7817P3.jsonl.
import itertools
import random
from horowitz_sahni_algorithm import horowitz_sahni_algorithm, sorted_sums
def has_subset(a: list[int], t: int) -> bool:
return any(sum(c) == t for r in range(len(a) + 1) for c in itertools.combinations(a, r))
def check(a: list[int], t: int) -> None:
got = horowitz_sahni_algorithm(a, t)
if got is None:
assert not has_subset(a, t)
else:
assert got == sorted(set(got))
assert all(0 <= k < len(a) for k in got)
assert sum(a[k] for k in got) == t
def test_example() -> None:
a = [7, 11, 2, 9, 5, 14]
assert [v for v, _ in sorted_sums(a, 0, 3)] == [0, 2, 7, 9, 11, 13, 18, 20]
assert [v for v, _ in sorted_sums(a, 3, 6)] == [0, 5, 9, 14, 14, 19, 23, 28]
assert horowitz_sahni_algorithm(a, 27) == [1, 2, 5]
assert horowitz_sahni_algorithm(a, 24) is None
def test_edges() -> None:
assert horowitz_sahni_algorithm([], 0) == []
assert horowitz_sahni_algorithm([], 5) is None
assert horowitz_sahni_algorithm([5], 5) == [0]
assert horowitz_sahni_algorithm([5], 0) == []
assert horowitz_sahni_algorithm([5], 4) is None
assert horowitz_sahni_algorithm([3, 3, 3, 3], 9) is not None
assert horowitz_sahni_algorithm([3, 3, 3, 3], 7) is None
assert horowitz_sahni_algorithm([-4, 6, -1], -5) == [0, 2]
big = [2**62, 2**62, 2**62, -(2**63)]
check(big, 2**62)
check(big, 3 * 2**62)
check(big, 1)
def test_sorted_sums_against_brute_force() -> None:
rng = random.Random(74)
for _ in range(200):
a = [rng.randrange(-20, 21) for _ in range(rng.randrange(0, 7))]
got = sorted_sums(a, 0, len(a))
assert [v for v, _ in got] == sorted(sum(c) for r in range(len(a) + 1) for c in itertools.combinations(a, r))
assert sorted(m for _, m in got) == list(range(2 ** len(a)))
assert all(v == sum(a[k] for k in range(len(a)) if m >> k & 1) for v, m in got)
def test_against_brute_force() -> None:
rng = random.Random(1974)
for _ in range(800):
n = rng.randrange(0, 11)
lo = rng.choice([0, -15])
a = [rng.randrange(lo, 30) for _ in range(n)]
t = rng.randrange(-20, 80)
check(a, t)
What the next level needs
- the tests did not run in this build