<p>Given an integer <code>n</code>, return all the numbers in the range <code>[1, n]</code> sorted in lexicographical order.</p>

<p>You must write an algorithm that runs in&nbsp;<code>O(n)</code>&nbsp;time and uses <code>O(1)</code> extra space.&nbsp;</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> [1,10,11,12,13,2,3,4,5,6,7,8,9]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 2
<strong>Output:</strong> [1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Solution {
    vector<int> result;
public:
    void lexicalOrderHelper(int start, int maxval, int curlen, int maxlen)
    {
        if (curlen > maxlen)
            return;
        int mind = start == 0 ? 1 : 0;
        for (int d = mind; d < 10; ++d) {
            int val = start + d;
            if (val <= maxval) {
                result.push_back(val);
                if (curlen+1 <= maxlen)
                    lexicalOrderHelper(val * 10, maxval, curlen+1, maxlen);
            } else {
                break;
            }
        }
    }

    int calcMaxlen(int n)
    {
        int maxlen = 1;
        for (int val = 9; val < n; val *= 10)
            maxlen++;
        return maxlen;
    }

    // 1 <= n <= 5 * 10^4  (50000)
    vector<int> lexicalOrder(int n)
    {
        int maxlen = calcMaxlen(n);
        int val = 0;
        int val1, val2, val3, val4, val5;
        for (int d1 = 1; d1 < 10; d1++) {
            val1 = val + d1;
            if (val1 > n)
                break;
            result.push_back(val1);
            for (int d2 = 0; maxlen > 1 && d2 < 10; d2++) {
                val2 = val1 * 10 + d2;
                if (val2 > n)
                    break;
                result.push_back(val2);
                for (int d3 = 0; maxlen > 2 && d3 < 10; ++d3) {
                    val3 = val2 * 10 + d3;
                    if (val3 > n)
                        break;
                    result.push_back(val3);
                    for (int d4 = 0; maxlen > 3 && d4 < 10; ++d4) {
                        val4 = val3 * 10 + d4;
                        if (val4 > n)
                            break;
                        result.push_back(val4);
                        for (int d5 = 0; maxlen > 4 && d5 < 10; ++d5) {
                            val5 = val4 * 10 + d5;
                            if (val5 > n)
                                break;
                            result.push_back(val5);
                        }
                    }
                }
            }
        }
        return result;
    }
};

12950