# Subset Sum in Almost-Linear Time

Preprint · Ce Jin, Xiao Mao

- Archive id: arxiv:2610.20742
- Published: 2026-10-14
- arXiv: https://arxiv.org/abs/2610.20742
- Source URL: https://arxiv.org/abs/2610.20742
- PDF: https://arxiv.org/pdf/2610.20742
- Provenance: arxiv

## Abstract

We give a deterministic algorithm for finding a subset of the input integers $1\\le a\_1,\\ldots,a\_n \\le Δ$ that sums to the target $t$ in $\\mathcal{O}(n+Δ^{1+o(1)})$ time. This improves upon the previous $\\widetilde{\\mathcal{O}}(n + Δ^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on $Δ$ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.