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 program
def countRec ( n , sum ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return ( sum == 0 ) NEW_LINE DEDENT if ( sum == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT if ( sum - i >= 0 ) : NEW_LINE INDENT ans = ans + countRec ( n - 1 , sum - i ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def finalCount ( n , sum ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( 1 , 10 ) : NEW_LINE INDENT if ( sum - i >= 0 ) : NEW_LINE INDENT ans = ans + countRec ( n - 1 , sum - i ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT n = 2 NEW_LINE sum = 5 NEW_LINE print ( finalCount ( n , sum ) ) NEW_LINE