Find all N-digit numbers with given sum of digits

Find all N-digit numbers with equal sum. N varies from [1 to 9] and sum <= 81 (Maximum possible sum in a 9-digit number).


 

For example,

3-digit numbers with sum 6 are
105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600

 

5-digit numbers with sum 42 are
69999 78999 79899 79989 79998 87999 88899 88989 88998 89799 89889 89898 89979 89988 89997 96999 97899 97989 97998 98799 98889 98898 98979 98988 98997 99699 99789 99798 99879 99888 99897 99969 99978 99987 99996

 
A simple solution would be to generate all N-digit numbers and print only those numbers that satisfies the given constraints. The complexity of this solution would be exponential.

A better solution would be to generate only those N-digit numbers that satisfies the given constraints. The idea is to use recursion. At each point in the recursion, we append digits from 0 to 9 to the partially formed number and recurse with one less digit. One special case we need to handle that the number should not start with 0. We also maintain sum of digits so far in the partially formed number. The optimization here is if sum of digits so far is more than the given sum at any point in the recursion, we return. We will solve this problem in Bottom-Up manner i.e. we start from first index and recursively fill the digits from left to right.

C

Download   Run Code

C++

Download   Run Code

Java

Download   Run Code

Output:

105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Top Coder
Guest

nicely done
。◕‿◕。

Rat
Guest

what is complexity of this solution?

yndi
Guest

O(10^n) time, O(n) space

Kevin
Guest

Nice and short recursive code (y)

yndi
Guest

I was thinking of a different approach. Imagine you already know one solution. Then, if you decrement one digit by one and increment any of the remaining ones, that will provide you another solution. This also provides a nice recursive structure. With some heuristic to find the first solution, it seems (but I’m too lazy to check/prove) it’s possible to decrease the runtime complexity from O(10^n) to O(n^2).