Simple Java DFS Solution (beats 85%, 12 lines)

• ``````
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++){
// 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);
}
}
}
``````

• @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???

``````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++){