7桁まではまあまあだが8桁以上だと遅いので、Cで書き換えると9桁でも瞬時に終わった。
(出力をファイルにリダイレクトした場合)。Visual Studioでは動作するが、
ideone.comでは変なコンパイラエラーが発生する。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void g(int a, int b, int s, int n, int t, int x)
{
　　int d, i;

　　if (n == 0) {
　　　　if (t == s && x >= a && x <= b) printf("%d\n", x);
　　} else {
　　　　for (d = i = 1; i < n; i++) d *= 10;
　　　　for (i = max(0, (s - t) - 9 * (n - 1)); i <= min(9, s - t); i++) {
　　　　　　g(a, b, s, n - 1, t + i, d * i + x);
　　　　}
　　}
}

void f(int a, int b, int s)
{
　　g(a, b, s, ceil(log10(b)), 0, 0);
}

int main(void)
{
　　f(1, 1000000000, 12);
　　return 0;
}