Count of n digit numbers whose sum of digits equals to given sum | A Java memoization based recursive program to count numbers with sum of n as 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 program to test above function
class sum_dig { static int lookup [ ] [ ] = new int [ 101 ] [ 501 ] ; static int countRec ( int n , int sum ) { if ( n == 0 ) return sum == 0 ? 1 : 0 ; if ( lookup [ n ] [ sum ] != - 1 ) return lookup [ n ] [ sum ] ; int ans = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) if ( sum - i >= 0 ) ans += countRec ( n - 1 , sum - i ) ; return lookup [ n ] [ sum ] = ans ; } static int finalCount ( int n , int sum ) { for ( int i = 0 ; i <= 100 ; ++ i ) { for ( int j = 0 ; j <= 500 ; ++ j ) { lookup [ i ] [ j ] = - 1 ; } } int ans = 0 ; for ( int i = 1 ; i <= 9 ; i ++ ) if ( sum - i >= 0 ) ans += countRec ( n - 1 , sum - i ) ; return ans ; } public static void main ( String args [ ] ) { int n = 3 , sum = 5 ; System . out . println ( finalCount ( n , sum ) ) ; } }