Count numbers ( smaller than or equal to N ) with given digit sum |  ; N can be max 10 ^ 18 and hence digitsum will be 162 maximum . ; If sum_so_far equals to given sum then return 1 else 0 ; Our constructed number should not become greater than N . ; If tight is true then it will also be true for ( i + 1 ) digit . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long dp [ 18 ] [ 2 ] [ 162 ] ; long long solve ( int i , bool tight , int sum_so_far , int Sum , string number , int len ) { if ( i == len ) { if ( sum_so_far == Sum ) return 1 ; else return 0 ; } long long & ans = dp [ i ] [ tight ] [ sum_so_far ] ; if ( ans != -1 ) { return ans ; } ans = 0 ; bool ntight ; int nsum_so_far ; for ( char currdigit = '0' ; currdigit <= '9' ; currdigit ++ ) { if ( ! tight && currdigit > number [ i ] ) { break ; } ntight = tight || currdigit < number [ i ] ; nsum_so_far = sum_so_far + ( currdigit - '0' ) ; ans += solve ( i + 1 , ntight , nsum_so_far , Sum , number , len ) ; } return ans ; } int main ( ) { long long count = 0 ; long long sum = 4 ; string number = "100" ; memset ( dp , -1 , sizeof dp ) ; cout << solve ( 0 , 0 , 0 , sum , number , number . size ( ) ) ; return 0 ; }