Count of n digit numbers whose sum of digits equals to given sum | Recursive function to count ' n ' digit numbers with sum of digits as ' sum ' . This function considers leading 0 's also as digits, that is why not directly called ; Base case ; Initialize answer ; Traverse through every digit and count numbers beginning with it using recursion ; This is mainly a wrapper over countRec . It explicitly handles leading digit and calls countRec ( ) for remaining digits . ; Initialize final answer ; Traverse through every digit from 1 to 9 and count numbers beginning with it ; Driver Code
< ? php function countRec ( $ n , $ sum ) { if ( $ n == 0 ) return $ sum == 0 ; if ( $ sum == 0 ) return 1 ; $ ans = 0 ; for ( $ i = 0 ; $ i <= 9 ; $ i ++ ) if ( $ sum - $ i >= 0 ) $ ans += countRec ( $ n - 1 , $ sum - $ i ) ; return $ 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 = 2 ; $ sum = 5 ; echo finalCount ( $ n , $ sum ) ; ? >