Solution:

Each carry in an addition replaces $10$ in one place by $1$ in the next, lowering the digit sum by $9.$ Hence $s(n + 864) = s(n) + s(864) - 9c = 20 + 18 - 9c,$ where $c$ is the number of carries, and $s(n + 864) = 20$ forces $c = 2.$ For a three-digit candidate $n$ with digits $t,$ $u,$ $v$ summing to $20:$ since $u + v \le 18,$ we have $t \ge 2,$ so the hundreds place always carries ($t + 8 \ge 10$), and exactly one of the units and tens places carries.

If the units carry and the tens do not, the tens computation $u + 6 + 1$ must stay below $10,$ so $u \le 2;$ then $t = 20 - u - v \ge 20 - 2 - 9 = 9,$ forcing $n = 929.$ If the tens carry and the units do not, then $v + 4 \le 9$ gives $v \le 5,$ so $t = 20 - u - v \ge 20 - 9 - 5 = 6,$ and $t = 6,$ $u = 9,$ $v = 5$ works: $n = 695.$

Indeed $s(695) = 20$ and $695 + 864 = 1559$ with $s(1559) = 20,$ so the smallest such $n$ is $695.$