First Harshad number with given sum
You solve the following more general problem: find the least number $N$ with sum of digits $T$ such that $N \mod M = R$ (the inputs are $M,T,R$). Initially, $T=M=S$ and $R=0$. Now you go over all possible least significant digits $b$. Using the formula
$$
(10n+b) \pmod{M} = 10(n \pmod{M}) + (b \pmod{M}),
$$
you reduce the problem to a smaller one, and so on.

The total amount of work appears to be $O(S^2)$, since the number of possible values for $T$ and $R$ is $O(S^2)$. Care needs to be taken with zero digits, however, a detail which I leave you to ponder.