剑指 Offer 17. 打印从1到最大的n位数

题目：剑指 Offer 17. 打印从1到最大的n位数

解题思路1：(非考点，不推荐这么写)

python无需考虑大数越界问题，直接一路输出即可

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        for i in range(1, 10 ** n):
            res.append(i)
        return res
        # return [i for i in range(1, 10 ** n)]
        # return list(range(1, 10 ** n))

优质解答：全排列递归求解（参考自K神）

固定高位，递归打印后面的数字。设置开始位start，将数字的高位0去除；设置检测值nine，当该位到达9后，下一个数字需要进位，此时控制start-1，即前移一位，回溯时需要将nine-1回到前一位。最后在将字符串转化为int放入列表中。

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        def dfs(x):
            if x == n:
                s = ''.join(num[self.start:])
                if s != '0':    res.append(int(s))
                if n - self.start == self.nine:    self.start -= 1
                return
            for i in range(10):
                if i == 9:    self.nine += 1
                num[x] = str(i)
                dfs(x+1)
            self.nine -= 1

        num, res = ['0'] * n, []
        self.nine = 0
        self.start = n - 1
        dfs(0)
        return res