全排列，DFS，回溯

题目链接-来源：力扣（LeetCode）

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

思路：

鉴于LeetCode中本题只需输出int，可知n不存在越界可能。只要实现一个关于整数的n次幂的计算方法，对任意n调用 pow(10, n) ，再从1开始循环打印即可。
拓展：
当然对于更广泛的使用场景而言（也是本题真正的考点），我们要考虑大数越界的情况，即输入的n可能是一个 long 型大数，甚至是一个类似 __uint128_t 的大数。那么我们需要借助不限长度的字符串，帮助我们实现数字的打印。
于是问题转化成，「输出n位 ‘0’~’9’数字的全排列」，我们可以用回溯算法+ DFS 来解决此类字符串的拼接、遍历问题。
对于函数的主体 DFS(n)，算法结构如下：

  • 对于每一位数字，我们在字符串中加上它，然后继续对其下一位使用 DFS(n - 1)，待返回后，「恢复现场」，将这位数字删除，进入下一个循环（依次遍历’0’ ~ ‘9’）。
  • 如果到达末位（n = 1），我们要输出拼接好的数字，然后返回。
    实操中，你可以从低位向高位遍历，也可以从高位向低位遍历（我采用后者）。但无论哪种方向，都有一个问题，遍历过程中高位会出现不该有的 ‘0’ （如 09，005，0003等）。当然对于本题，由于返回的是int[]类型，只需调用 parseInt() 不存在这种麻烦，如果题目要求我们按 String 返回，就需要额外考虑 ‘0’ 了，当然代码也不负责，只是稍显繁琐。我的实现中考虑了这种情况。
    时间复杂度：O(10^n)
    空间复杂度：O(10^n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int[] printNumbers(int n) {
        res = new int [(int) Math.pow(10, n) - 1];
        sb = new StringBuilder();
        count = res.length - 1;
        dfs(n);
        return res;
    }
    private int[] res;
    private int count;
    private StringBuilder sb;
    
    private void dfs(int n) {
        if (count < 0) {
            return;
        }
        
        for (int i = 9; i > 0; i--) {
            sb.append(i);
            if (n == 1) {
                res[count--] = Integer.parseInt(sb.toString());
            } else {
                dfs(n - 1);
            }
            sb.deleteCharAt(sb.length() - 1);
        }
        
        if (sb.length() != 0) {
            sb.append(0);
        }
        if (n == 1 && count >= 0) {
            res[count--] = Integer.parseInt(sb.toString());
        } else {
            dfs(n - 1);
        }
        if (sb.length() > 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}