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 204 213 222 231 303 312 321 402 411 501

 

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 recuse 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

Output:

105 114 123 132 141 204 213 222 231 303 312 321 402 411 501

 

C++

Download   Run Code

Output:

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


 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Aditya Goel
Member

nicely done 👍👍
。◕‿◕。

Rat
Guest

what is complexity of this solution?

wpDiscuz