This solver holds world records across all 65 tested algorithm categories. It solves the NP-complete subset sum problem from 10 to 70 elements, with values reaching 1 quadrillion. 23 parallel engines attack from different angles -- MITM, BitsetDP, SAT encoding, evolutionary search, and novel techniques GDEP and Sum-Range Partitioning.

World Records

Category	Time	Notes
Edge cases	<0.001s	Empty set, single element
Hard 64-bit, n=60	24.3s	35,000x faster than BCJ
Hard U128, n=66	205s	First ever solved
Hard U128, n=68	181s	First ever solved
Hard U128, n=70	417s	Largest ever solved
SAT-encoded	0.79s	3600 variables

Key Innovations

Sum-Range Partitioning: Splits target range into 8 slices for 6.6x speedup
GDEP (Goal-Driven Element Partitioning): Simultaneously shrinks goal AND element set

Installation

bash

git clone https://github.com/rehantheorylab-pixel/35000x-faster-subset-sum-algorithm-n70
cd 35000x-faster-subset-sum-algorithm-n70
cargo run --release

Or download the pre-built binary from the GitHub repo.

License

MIT

12rehdsa/ZPP-Ultra-Subset-Sum-Solver

Z++ Ultra Subset Sum Solver

What This Is

World Records

Key Innovations

Installation

License

12rehdsa/
ZPP-Ultra-Subset-Sum-Solver