17. print from 1 to the maximum n digits

The finger of the sword Offer 17. Print from 1 To the biggest n digit

Ideas ： Divide and conquer algorithm / Full Permutation

For Large Print , Consider that large numbers are out of bounds . So we need to solve ：

1. Represents the variable type of a large number ：string
2. Generate a string set of numbers ：int Carry of type cannot be applied to string type , Consider using n Bit 0-9 The whole arrangement , It can avoid carry operation
3. Recursively generate a full permutation ： Based on the idea of divide and conquer algorithm , Fix the high position first , Recursion to low position , When all bits are fixed , Add string

class Solution {
public:
    vector<int> nums;
    string s;
    vector<int> printNumbers(int n) {
        s.resize(n);
        dfs(n,0);
        return nums;
    }

    void dfs(int end,int index){
        if(end==index){
            int i=0;
            while(i<s.size()&&s[i]=='0')++i;
            if(i!=s.size())
                nums.push_back(stoi(s.substr(i)));
            return;
        }

        for(int i=0;i<=9;++i){
            s[index]='0'+i;
            dfs(end,index+1);
        }
    }
};

Time complexity O($10^n$)

Spatial complexity O(n)