  We consider the canonical Subset Sum problem: given a list of positive
integers $a_1,\ldots,a_n$ and a target integer $t$ with $t > a_i$ for all $i$,
determine if there is an $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$.
The well-known pseudopolynomial-time dynamic programming algorithm [Bellman,
1957] solves Subset Sum in $O(nt)$ time, while requiring $\Omega(t)$ space.
  In this paper we present algorithms for Subset Sum with $\tilde O(nt)$
running time and much lower space requirements than Bellman's algorithm, as
well as that of prior work. We show that Subset Sum can be solved in $\tilde
O(nt)$ time and $O(\log(nt))$ space with access to $O(\log n \log \log n+\log
t)$ random bits. This significantly improves upon the $\tilde O(n
t^{1+\varepsilon})$-time, $\tilde O(n\log t)$-space algorithm of Bringmann
(SODA 2017). We also give an $\tilde O(n^{1+\varepsilon}t)$-time,
$O(\log(nt))$-space randomized algorithm, improving upon previous
$(nt)^{O(1)}$-time $O(\log(nt))$-space algorithms by Elberfeld, Jakoby, and
Tantau (FOCS 2010), and Kane (2010). In addition, we also give a $\mathrm{poly}
\log(nt)$-space, $\tilde O(n^2 t)$-time deterministic algorithm.
  We also study time-space trade-offs for Subset Sum. For parameter $1\le k\le
\min\{n,t\}$, we present a randomized algorithm running in $\tilde O((n+t)\cdot
k)$ time and $O((t/k) \mathrm{polylog} (nt))$ space.
  As an application of our results, we give an
$\tilde{O}(\min\{n^2/\varepsilon, n/\varepsilon^2\})$-time and
$\mathrm{polylog}(nt)$-space algorithm for "weak" $\varepsilon$-approximations
of Subset Sum.
