Let your recursion function is "void dfs1(int k, int curr)", k is digit, curr is current S, then use it code:

    int start = 0;
    start = max(start, curr - 9 * (k - 1));

    int end = min(9, curr);
    if(k == 10) {
        end = min(1, end);
    }

    for(int i = start; i <= end; i++) {
        dfs1(k - 1, curr - i);
    }

It turns out, curr does not go beyond zero at k = 0!
I have 937ms with this solution

But with precalc I have 31ms :)
Good luck