Equal-subset-sum faster than the meet-in-the-middle

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)
34 Downloads (Pure)


In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B ⊆ S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O(3n/2) ≤ O(1.7321n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O(1.7088n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O(3n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O(2.6817n) time and polynomial space.

Original languageEnglish
Title of host publication27th Annual European Symposium on Algorithms, ESA 2019
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages16
ISBN (Electronic)978-3-95977-124-5
Publication statusPublished - Sept 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sept 201911 Sept 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference27th Annual European Symposium on Algorithms, ESA 2019


  • Enumeration technique
  • Equal-Subset-Sum
  • Meet-in-the-middle
  • Randomized algorithm
  • Subset-Sum
  • meet-in-the-middle
  • randomized algorithm
  • enumeration technique


Dive into the research topics of 'Equal-subset-sum faster than the meet-in-the-middle'. Together they form a unique fingerprint.

Cite this