Count of n digit numbers whose sum of digits equals to given sum | A C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; unsigned long long int lookup [ 101 ] [ 501 ] ; unsigned long long int countRec ( int n , int sum ) { if ( n == 0 ) return sum == 0 ; if ( lookup [ n ] [ sum ] != -1 ) return lookup [ n ] [ sum ] ; unsigned long long 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 ; } unsigned long long int finalCount ( int n , int sum ) { memset ( lookup , -1 , sizeof lookup ) ; unsigned long long int ans = 0 ; for ( int i = 1 ; i <= 9 ; i ++ ) if ( sum - i >= 0 ) ans += countRec ( n - 1 , sum - i ) ; return ans ; } int main ( ) { int n = 3 , sum = 5 ; cout << finalCount ( n , sum ) ; return 0 ; }