Problem Statement

Given two integers ‘n’ and ‘sum’, find count of all n digit numbers with sum of digits as ‘sum’. Leading 0’s are not counted as digits. 1 <= n <= 100 and 1 <= sum <= 500

Example:

Input:  n = 2, sum = 2
Output: 2
Explanation: Numbers are 11 and 20

Input:  n = 2, sum = 5
Output: 5
Explanation: Numbers are 14, 23, 32, 41 and 50

Input:  n = 3, sum = 6
Output: 21

Problem Link

N digit numbers with digit sum S - InterviewBit

Reference Link

Count of n digit numbers whose sum of digits equals to given sum - GeeksforGeeks

Approach

The idea is simple, we subtract all values from 0 to 9 from given sum and recur for sum minus that digit. Below is recursive formula.

    countRec(n, sum) = ∑countRec(n-1, sum-x)
                            where 0 =< x = 0

    One important observation is, leading 0's must be
    handled explicitly as they are not counted as digits.
    So our final count can be written as below.
    finalCount(n, sum) = ∑countRec(n-1, sum-x)
                           where 1 =< x = 0

Code

//Top Down Memoization
#define mod 1000000007
vector<vector<long long int>> dp;

long long int recur(int n,int sum)
{
    if(n==0)
    return dp[n][sum] = sum==0;
    
    if(dp[n][sum]!=-1)
    return dp[n][sum];
    
    long long int res = 0;
    for(int i=0;i<=9;i++)
    {
        if(sum-i>=0)
        res = (res + (recur(n-1,sum-i)%mod))%mod;
    }
    
    return dp[n][sum] = res;
}
int Solution::solve(int n, int sum) {
    
    dp.clear();
    dp.resize(n+1,vector<long long int>(sum+1,-1));
    
    long long int res = 0;
    for(int i=1;i<=9;i++)
    {
        if(sum-i>=0)
        res = (res + (recur(n-1,sum-i)%mod))%mod;
    }
    
    
    return res%mod;
    
    
}