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 final answer ; Traverse through every digit from 1 to 9 and count numbers beginning with it ; Driver Code
< ? php $ lookup = array_fill ( 0 , 101 , array_fill ( 0 , 501 , -1 ) ) ; function countRec ( $ n , $ sum ) { global $ lookup ; if ( $ n == 0 ) return $ sum == 0 ; if ( $ lookup [ $ n ] [ $ sum ] != -1 ) return $ lookup [ $ n ] [ $ sum ] ; $ ans = 0 ; for ( $ i = 0 ; $ i < 10 ; $ i ++ ) if ( $ sum - $ i >= 0 ) $ ans += countRec ( $ n - 1 , $ sum - $ i ) ; return $ lookup [ $ n ] [ $ sum ] = $ ans ; } function finalCount ( $ n , $ sum ) { $ ans = 0 ; for ( $ i = 1 ; $ i <= 9 ; $ i ++ ) if ( $ sum - $ i >= 0 ) $ ans += countRec ( $ n - 1 , $ sum - $ i ) ; return $ ans ; } $ n = 3 ; $ sum = 5 ; echo finalCount ( $ n , $ sum ) ; ? >