Count of n digit numbers whose sum of digits equals to given sum | A lookup table used for memoization ; Memoization based implementation of recursive function ; Base case ; If this subproblem is already evaluated , return the evaluated value ; Initialize answer ; Traverse through every digit and recursively count numbers beginning with it ; This is mainly a wrapper over countRec . It explicitly handles leading digit and calls countRec ( ) for remaining n . ; Initialize all entries of lookup table ; Initialize final answer ; Traverse through every digit from 1 to 9 and count numbers beginning with it ; Driver code
let lookup = new Array ( 101 ) ; function countRec ( n , sum ) { if ( n == 0 ) return sum == 0 ? 1 : 0 ; if ( lookup [ n ] [ sum ] != - 1 ) return lookup [ n ] [ sum ] ; let ans = 0 ; for ( let i = 0 ; i < 10 ; i ++ ) if ( sum - i >= 0 ) ans += countRec ( n - 1 , sum - i ) ; return lookup [ n ] [ sum ] = ans ; } function finalCount ( n , sum ) { for ( let i = 0 ; i < 101 ; i ++ ) { lookup [ i ] = new Array ( 501 ) ; for ( let j = 0 ; j < 501 ; j ++ ) { lookup [ i ] [ j ] = - 1 ; } } let ans = 0 ; for ( let i = 1 ; i <= 9 ; i ++ ) if ( sum - i >= 0 ) ans += countRec ( n - 1 , sum - i ) ; return ans ; } let n = 3 , sum = 5 ; document . write ( finalCount ( n , sum ) ) ;