Consider the DP:

f(0, sum) = abs(sum)
f(i, sum) = min(f(i-1, sum+a[i]). f(i-1, sum-a[i]))

Then think of the path of the DP that leads to the optimal solution. Since sum is minimized in the last step, maybe it's also small in every intermediate step? This is not always true. But what if we shuffle the array?

Then we can think of each $$$a_{i}$$$ as an independent random variable (which is not really true, but close enough for CP purposes), and sum might follow something like a random walk, which is normally distributed according to CLT. Due to linearity of variance of independent variables, we expect that $$$|\texttt{sum}|$$$ is always $$$O(\sqrt{N}\cdot\max\{ a_{i}\})$$$ with high probability.

So this means we can write above DP solution like this:

f(0, sum) = abs(sum)
f(i, sum) = if abs(sum) > LIMIT
              then INF
              else min(f(i-1, sum+a[i]). f(i-1, sum-a[i]))

(Where $$$\texttt{LIMIT} \in O(\sqrt{N}\cdot\max\{ a_{i}\})$$$ -- multiply by 3 or 4) And we still get the correct answer with high probability, assuming that a has been shuffled beforehand. With this method we a probabilistic solution with complexity $$$O(N^{1.5}\cdot\max\{ a_{i}\})$$$ instead of the classic $$$O(N^{2}\cdot\max\{ a_{i}\})$$$