> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0386-lexicographical-numbers.md).

# 0386. Lexicographical Numbers

<https://leetcode.com/problems/lexicographical-numbers>

## Description

Given an integer `n`, return all the numbers in the range `[1, n]` sorted in lexicographical order.

You must write an algorithm that runs in `O(n)` time and uses `O(1)` extra space.&#x20;

**Example 1:**

```
**Input:** n = 13
**Output:** [1,10,11,12,13,2,3,4,5,6,7,8,9]
```

**Example 2:**

```
**Input:** n = 2
**Output:** [1,2]
```

**Constraints:**

* `1 <= n <= 5 * 104`

## ac

It's more like a tricky math problem instead of practical algorithm problem.

<https://leetcode.com/problems/lexicographical-numbers/discuss/86231/Simple-Java-DFS-Solution>

```java
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <=9; i++) dfs(n, i, res);
        return res;
    }

    public boolean dfs(int n, int k, List<Integer> res) {
        // exit
        if (k > n) return false;
        if (k != 0) res.add(k);

        for (int i = 0; i <= 9; i++) {
            if (!dfs(n, k * 10 + i, res)) break;
        }

        return true;
    }
}

/*
10-nodes tree, pre-order traversal, same as #440
*/
```