386. Lexicographical Numbers

T: O(n)
S: O(logn (10 base, because 10 branch))

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            dfs(i, n, result);
        }
        return result;
    }
    private void dfs(int num, int n, List<Integer> result) {
        if (num > n || result.size() == n) {
            return;
        }
        result.add(num);
        for (int i = 0; i <= 9; i++) {
            dfs(num*10 + i, n, result);
        }
    }
}


/***
   1.  2.  3. 4..
   /\
   0~9 -> 1*10 + 0~9
   /\
  0~9

T: O(n)
S: O(logn (10 base, because 10 branch)), every level n will divide to 10 part

 */