386. Lexicographical Numbers

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.

class Solution {
    void helper(vector<int>& res, int n, int now) {
        if(now > n) return;
        res.push_back(now);
        for(int i = 0; i <= 9; i++)
            helper(res, n, now * 10 + i);
    }
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for(int i = 1; i <= 9; i++)
            helper(res, n, i);
        return res;
    }
};