Find the kth smallest number with sum of digits as m | C ++ implementation of the approach ; Recursively moving to add all the numbers upto a limit with sum of digits as m ; Max number of digits allowed in a number for this implementation ; Function to return the kth number with sum of digits as m ; The kth smallest number is found ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define int  long long NEW_LINE const int N = 2005 ; set < int > ans ; void dfs ( int num , int left , int ct ) { if ( ct >= 15 ) return ; if ( left == 0 ) ans . insert ( num ) ; for ( int i = 0 ; i <= min ( left , 9LL ) ; i ++ ) dfs ( num * 10 + i , left - i , ct + 1 ) ; } int getKthNum ( int m , int k ) { dfs ( 0 , m , 0 ) ; int ct = 0 ; for ( auto it : ans ) { ct ++ ; if ( ct == k ) { return it ; } } return -1 ; } int main ( ) { int m = 5 , k = 3 ; cout << getKthNum ( m , k ) ; return 0 ; }