Description

Print numbers from 1 to the largest number with N digits by recursion.

Notice

It's pretty easy to do recursion like:

recursion(i) {
    if i 
>
 largest number:
        return
    results.add(i)
    recursion(i + 1)
}

however this cost a lot of recursion memory as the recursion depth maybe very large. Can you do it in another way to recursive with at most N depth?

Example

GivenN = 1, return[1,2,3,4,5,6,7,8,9].

GivenN = 2, return[1,2,3,4,5,6,7,8,9,10,11,12,...,99].

Solution

以二位数为例，10 ~ 99可以拆分为 （1~9）*10， （1~9）*10 + （1~9）
以三位数为例，100 ~ 999可以拆分为 （1 ~ 9） * 100， （1 ~ 9） * 100 + （1 ~ 99）
(1 ~ 9)是定的，（1 ~ 9）和（1 ~ 99）是已经在result中的数，拿出来加上就行。10和100也是固定的。

public class Solution {
    /**
     * @param n: An integer.
     * return : An array storing 1 to the largest number with n digits.
     */
    public List<Integer> numbersByRecursion(int n) {
        // write your code here
        List<Integer> result = new ArrayList<Integer>();
        numbersByRecursion(result, n);
        return result;
    }

    public int numbersByRecursion(List<Integer> result, int n) {
        if (n == 0) {
            return 1;
        }

        int base = numbersByRecursion(result, n - 1);
        int size = result.size();

        for (int i = 1; i <= 9; i++) {
            int num = base * i;
            result.add(num);
            for (int j = 0; j < size; j++) {
                result.add(num + result.get(j));
            }
        }

        return 10 * base;
    }
}