  We propose an $\widetilde{O}(n + 1/\eps)$-time FPTAS (Fully Polynomial-Time
Approximation Scheme) for the classical Partition problem. This is the best
possible (up to a polylogarithmic factor) assuming SETH (Strong Exponential
Time Hypothesis) [Abboud, Bringmann, Hermelin, and Shabtay'22]. Prior to our
work, the best known FPTAS for Partition runs in $\widetilde{O}(n +
1/\eps^{5/4})$ time [Deng, Jin and Mao'23, Wu and Chen'22]. Our result is
obtained by solving a more general problem of weakly approximating Subset Sum.
