Problem

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

Example

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

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

Note

只有当位数n >= 0时，才打印数字。首先分析边界n = 0，应该return 1，然后用base存最高位。用helper()函数对base进行递归运算，同时更新结果数组res。

res = {1, 2, 3, 4, 5, 6, 7, 8, 9};base = helper(n-1, res); //10//i = 1 ~ 9;for i:curbase = i * base; //10, 20, 30, 40, ... , 80, 90res.add(curbase); // 10; 20; ... ; 80; 90//j = index of res;for j:res.add(curbase + res.get(j)); //11, 12, 13, ... , 18, 19;                               //21, 22, 23, ... , 28, 29;                               //...

归纳一下，首先，计算最高位存入base，然后，用1到9倍的base（curbase）和之前res里已经存入的所有的数（res.size()个）循环相加，再存入res，更新res.size，计算更高位直到base等于10^n...

Solution

Recursion

public class Solution {    public List
    
      numbersByRecursion(int n) {        List
     
       res = new ArrayList
      
       ();        if (n >= 0) {            helper(n, res);        }        return res;    }    public int helper(int n, List
       
         res) {        if (n == 0) return 1;        int base = helper(n-1, res);        int size = res.size();        for (int i = 1; i <= 9; i++) {            int curbase = i * base;            res.add(curbase);            for (int j = 0; j < size; j++) {                res.add(curbase + res.get(j));            }        }        return base * 10;    }}
       
      
     
    

Non-recursion

public class Solution {    public List
    
      numbersByRecursion(int n) {        List
     
       res = new ArrayList
      
       ();        int max = 1;        while (n != 0) {            max *= 10;            n--;        }        for (int i = 1; i < max; i++) {            res.add(i);        }        return res;    }}