I've got a good method. Use the following recurrence eqn and solve using DP.
num(n,s)=sigma(i=0 to 9){ ((s-i)>=0)?num(n-1, s-i):0}
n represents the number of digits and s represents the sum of digits.

NOTE: For those who got WA#9, you would not have initialized num[1][9]=1. Better checkout the whole 2d array once and verify that for s=81 output should be 1.



Edited by author 15.02.2008 00:14