public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>(n);
// from 1 to 9.
// 0 is can't be a soution.
dfs(1, 9, n, res);
return res;
}
private void dfs(int start, int end, int n, List<Integer> res){
// <= n make the solution can't bigger than n
for (int i = start; i <= end && i <= n; i++){
res.add(i);
// 10 > next recursion: 100(>next recursion 1000), 101,102....
// next loop: 11 > next recursion: 110, 111,112....
// next loop: 12 > next recursion: 120, 121,122....
// from 0 to 9 different from the dfs call in method lexicalOrder
dfs(i * 10, i * 10 + 9, n, res);
}
}
}
Simple Java DFS Solution (beats 85%, 12 lines)


@Chung this solution is great. I don't know why it does not have upvotes. Can you provide a little explanation. I'm getting a little lost in the recursion. In the case of n = 13, when our for loop eventually fails because i is no longer less than n, start = 100 and end = 109. How in the world does start and end become 10 and 19 all over again???

@ElayMarco Here are some explanation. Hope this could help you
public class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> res = new ArrayList<>(n); // from 1 to 9. // 0 is can't be a soution. dfs(1, 9, n, res); return res; } private void dfs(int start, int end, int n, List<Integer> res){ // <= n make the solution can't bigger than n for (int i = start; i <= end && i <= n; i++){ res.add(i); // 10 > next recursion: 100(>next recursion 1000), 101,102.... // next loop: 11 > next recursion: 110, 111,112.... // next loop: 12 > next recursion: 120, 121,122.... // from 0 to 9 different from the dfs call in method lexicalOrder dfs(i * 10, i * 10 + 9, n, res); } } }