Faster Exact Algorithms for Equal-Subset-Sum
2026-07-10 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors focus on the Equal-Subset-Sum problem, where the goal is to find two different groups of numbers from a set that add up to the same total. They improved the best-known exact algorithm by making it faster and using less memory compared to previous work by Randolph and Węgrzycki. Additionally, they enhanced the fastest algorithm that uses only a reasonable amount of memory, improving on results from Mucha and colleagues. They also explored how to balance time and space more efficiently for solving this problem.
Equal-Subset-Sum problemexact algorithmsworst-case complexitytime complexityspace complexityexponential timepolynomial spacetime-space tradeoffssubset sumsalgorithm optimization
Authors
Ryosuke Yamano, Tetsuo Shibuya
Abstract
We study exact algorithms for Equal-Subset-Sum in the worst-case setting: given a set $S$ of $n$ integers, find two distinct subsets $A,B\subseteq S$ whose sums are equal. We establish a new state-of-the-art bound for this problem by improving the fastest known algorithm, due to Randolph and Węgrzycki (STOC 2026), from $O^*(1.7067^n)$ time and space to an algorithm that runs in $O^*(1.6994^n)$ time and uses $O^*(1.5664^n)$ space. We also improve the best known polynomial-space running time, due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), from $O^*(2.6817^n)$ to $O^*(2.5430^n)$. Finally, we investigate time-space tradeoffs for this problem and improve the running times achievable under a broad range of exponential-space bounds.