First Harshad number with given sum

How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits.

I think that some kind of dynamic programming should be used. But which one?

Thanks in advance for any ideas.

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.