I'm looking to generate all possible values of n-digit number, in the following order, where the sequence is dictated by the sum of the individual digits.
For example, with n = 3
:
111 sum = 3
112 sum = 4
121
211
122 sum = 5
212
221
113
131
311
114 sum = 6
141
411
:::
999 sum = 27
The order within the sum group is not important.
Any help, ideas would be appreciated
Best Answer
You can always turn a recursive problem into an iterative one if you maintain your own stack of important data - that's if the reason for avoiding recursion is that the language doesn't support it.
But, if the language does support it, then recursive solutions are far more elegant.
The only other reason I can think of for avoiding recursion is limited stack depth. In that case an iterative conversion of a recursive solution will mitigate the problem by not requiring as much stack space.
But you need to understand that the stack depth for processing n numbers only grows relative to log10n. In other words, you only get an extra stack frame per digit (only 10 stack frames to handle the full range of 32-bit integers).
Aside: by the time you get to that point, you're algorithm will be taking so long to run, stack frames will be the least of your problems :-)
Here's a recursive Python solution:
which outputs (for 2 and 3):
Keep in mind that solution could still be optimized somewhat - I left it in its initial form to show how elegant recursion can be. A pure-iterative solution follows, but I still prefer the recursive one.
Run the following program and use
sort
andawk
under UNIX to get the desired order. For example:Note that this uses external tools to do the sorting but you could just as easily sort within the C code (memory permitting).