The subset sum problem is NP-complete. Given integers, find a subset that sums to a target. Simple to state -- exponentially hard to solve.
I built a solver that's 35,000x faster than previous approaches. It holds world records across all 65 test categories. First solver to reach n=70 with 1 quadrillion values.
How It Works
23 parallel engines attack the problem simultaneously. The moment any engine finds the answer, all others stop. You fire everything at once and the best one wins.
Sum-Range Partitioning: The key breakthrough. Split the target range into 8 slices, each on its own thread with zero shared state. 6.6x speedup on 8 cores.
GDEP Engine: My newest engine. After picking an element, dynamically restricts the pool to only values smaller than the remainder. Shrinks both goal AND element set simultaneously.
Performance:
- n=40: 0.1s
- n=60: 24s (BCJ would take ~240 hours -- 35,000x faster)
- n=70: 417s (world record)
Try It
Live demo: https://subsetsolver.netlify.app
GitHub: https://github.com/rehantheorylab-pixel/35000x-faster-subset-sum-algorithm-n70
Zenodo DOI: 10.5281/zenodo.20399806
Open source. MIT license. Built by Rehan.
Top comments (0)