The latest articles on DEV Community by Rehan Muhammad (@rehantheorylabpixel). https://dev.to/rehantheorylabpixel https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F3953038%2Fe49997cb-8f34-435d-b591-7dd2747aaee3.png https://dev.to/rehantheorylabpixel en Rehan Muhammad Tue, 26 May 2026 18:04:02 +0000 https://dev.to/rehantheorylabpixel/i-built-a-subset-sum-solver-35000x-faster-than-previous-approaches-31ic https://dev.to/rehantheorylabpixel/i-built-a-subset-sum-solver-35000x-faster-than-previous-approaches-31ic <p>The subset sum problem is NP-complete. Given integers, find a subset that sums to a target. Simple to state, exponentially hard to solve.</p> <p>I built a solver that races <strong>49 engines</strong> against every instance - published baselines and original methods - and reports which engine produced the answer.</p> <h2> How it works </h2> <p>Every applicable engine attacks the problem at once. The first to find the answer wins, and the winner is reported. That second part matters: you do not just get an answer, you learn which class of technique solved that class of instance.</p> <p>Published baselines included for comparison: Schroeppel-Shamir, meet-in-the-middle (Horowitz-Sahni), BCJ, HGJ, ColumnSAT, Bonnetain, bitset DP.</p> <p>Original engines: GDEP (Goal-Driven Element Partitioning), adaptive core-aware partitioning, and arbitrary-precision (BigUint) paths for values beyond u128.</p> <h2> What the numbers actually are </h2> <ul> <li> <strong>n=60, 64-bit: 524 s on an Intel i3-2100</strong> - measured, 1,649x faster than BCJ's published runtime of 864,000 s (10 days)</li> <li>n=60 on a Ryzen 9: <strong>24.3 s projected</strong> - that would be roughly 35,500x, but it is a projection, not a measurement</li> <li>Memory floor: <strong>~12 GB at n=60</strong>. Below that the machine thrashes and runs 3-4x slower.</li> </ul> <p>Note: 864,000 is BCJ's runtime in seconds, not a speedup. The ratio is that figure divided by my time.</p> <h2> What this does not claim </h2> <ul> <li>Baselines are quoted from publication, not re-measured on the same machine. A true head-to-head is still outstanding.</li> <li>No world records. The 65 categories are categories I defined; they measure coverage of my own suite.</li> <li>GPU support is detection only - all computation runs on CPU cores.</li> </ul> <p>Code: <a href="https://github.com/rehantheorylab-pixel/zpp-subset-sum-solver" rel="noopener noreferrer">https://github.com/rehantheorylab-pixel/zpp-subset-sum-solver</a></p> algorithms rust python performance