CS-Notes 剑指 Offer 题解：打印从 1 到最大的 n 位数——char 数组存储与回溯法实现

2026-09-06 11:31:32作者：伍希望

本文围绕 CS-Notes 仓库中《剑指 Offer》题解的第 17 题“打印从 1 到最大的 n 位数”展开，完整讲解这道题的题面、为什么必须用 char 数组代替整型存储、以及基于回溯法的完整 Java 实现。读完本文，你将掌握回溯法生成“全排列式”候选序列的标准模板、前导零的处理技巧、以及该算法的时间/空间复杂度推导，并能将其迁移到仓库中其他同模板的回溯题目。

题目描述

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

原始题解见 [notes/17. 打印从 1 到最大的 n 位数.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/17. 打印从 1 到最大的 n 位数.md?utm_source=gitcode_repo_files)。

题目本身只有一行描述，但有两个隐藏约束：

打印必须按数值递增顺序（1, 2, 3, ... 999），而不是按字典序随意输出；
n 可能非常大，大到任何基本整型都放不下 10^n - 1。

为什么不能用 int，而要用 char 数组

如果 n 比较小（比如 n ≤ 9），可以直接用 for (int i = 1; i <= Math.pow(10, n) - 1; i++) 循环打印。但题目明确指出“n 可能会非常大”，此时最大的 n 位数会超出 long 甚至 BigInteger 的常用场景范围，整型方案在理论上就失去了通用性。

因此题解采用的策略是：不真正“算出”这些数字，而是把它们当成定长数字串来枚举。用一个长度为 n 的 char 数组 number，每一位存放 '0' ~ '9' 中的一个字符，这样无论 n 多大，存储成本始终只有 O(n) 个字符。原文明确给出这一思路：

由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。使用回溯法得到所有的数。

这本质上是把“1 到最大的 n 位数”转化为：在一个 n 位的“数字拨盘”上，每一位独立地取 0~9，共 10 种选择，枚举所有 10^n 种组合，其中全 0 组合（即 "00...0"）打印出来恰好是 0，而题目要求从 1 开始——但原实现的处理方式是打印时跳过前导零，让 "00...0" 与 "00...01" 等前导零组合都归一化输出，最终得到 1 到 999...（n 个 9）的递增序列（配合按位枚举的顺序，输出天然递增，见下文执行过程分析）。

完整回溯法实现

以下是原文档给出的完整 Java 代码，保持原样继承：

public void print1ToMaxOfNDigits(int n) {
    if (n <= 0)
        return;
    char[] number = new char[n];
    print1ToMaxOfNDigits(number, 0);
}

private void print1ToMaxOfNDigits(char[] number, int digit) {
    if (digit == number.length) {
        printNumber(number);
        return;
    }
    for (int i = 0; i < 10; i++) {
        number[digit] = (char) (i + '0');
        print1ToMaxOfNDigits(number, digit + 1);
    }
}

private void printNumber(char[] number) {
    int index = 0;
    while (index < number.length && number[index] == '0')
        index++;
    while (index < number.length)
        System.out.print(number[index++]);
    System.out.println();
}

代码逐段拆解

1. 入口方法：参数校验与数组初始化

print1ToMaxOfNDigits(int n) 是对外入口：

n <= 0 时直接返回，防御非法输入；
分配长度为 n 的 char[] number 作为“数字拨盘”；
从下标 digit = 0（最高位）开始递归。

注意这里没有对每一位的候选值做“剪枝”——每一位都可以是 0~9，包括最高位。也就是说递归树会枚举出 "000"、"001"、"010" 这类带前导零的组合，合法性交给打印阶段处理。

2. 递归搜索：标准的回溯模板

print1ToMaxOfNDigits(char[] number, int digit) 是典型的回溯法结构，可拆成四个要素：

要素	对应代码	说明
参数	`char[] number`, `int digit`	`digit` 表示当前正在填充的是第几位（从 0 即最高位开始）
结束条件	`if (digit == number.length)`	n 位全部填充完毕，调用 `printNumber` 输出一个完整的 n 位串
选择列表	`for (int i = 0; i < 10; i++)`	当前位取 `'0'` ~ `'9'` 共 10 个候选
做出选择 / 撤销选择	`number[digit] = (char) (i + '0')` 后递归	注意这里没有显式回写（如递归后把 `number[digit]` 复原），因为下一轮循环或上一层递归返回后该位置都会被重新赋值，无需显式撤销

递归从最高位逐位向低位推进：digit 每加 1 就深入一层，digit 达到 number.length 时说明一条从最高位到最低位的完整路径已经确定，即完成了一个 n 位串（含前导零）的枚举，调用 printNumber 打印。

这个模板与仓库中其他回溯题完全同构：[notes/12. 矩阵中的路径.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/12. 矩阵中的路径.md?utm_source=gitcode_repo_files) 里对回溯法的定义是“它是一次暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程”——本题的“状态”就是 char[] number 中每一位的赋值；[notes/38. 字符串的排列.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/38. 字符串的排列.md?utm_source=gitcode_repo_files) 则展示了带 hasUsed 标记与显式撤销（s.deleteCharAt）的变体。本题因为“覆盖式写值”，省略了显式撤销步骤。

3. 打印方法：跳过前导零

printNumber(char[] number) 处理前导零归一化：

private void printNumber(char[] number) {
    int index = 0;
    while (index < number.length && number[index] == '0')
        index++;
    while (index < number.length)
        System.out.print(number[index++]);
    System.out.println();
}

第一个 while 定位第一个非 '0' 字符的下标；
第二个 while 从该下标打印到末尾；
若全是 '0'（即 "00...0"），index 会走到数组末尾，循环体不执行，只打印一个空行，即输出数字 0。

配合按位枚举的递归顺序（最高位变化最慢，最低位变化最快，等价于一个 10 进制计数器的 0→9 逐位进位），输出序列是 0, 1, 2, ..., 999。题目要求从 1 开始打印，实际使用时可在 printNumber 中过滤掉全零这一种情况（例如打印前判断 index == number.length 时直接返回），这是原实现留白给读者注意的边界点。

4. 执行过程示例（n = 2）

以 n = 2 为例，递归树的展开顺序等价于下表（每一行是 digit == 2 时刻的 number 内容与打印结果）：

number 数组状态	打印结果
`{'0','0'}`	0（空行）
`{'0','1'}`	1
`{'0','2'}`	2
...	...
`{'0','9'}`	9
`{'1','0'}`	10
`{'1','1'}`	11
...	...
`{'9','9'}`	99

可以看到输出按数值严格递增，满足“按顺序打印”的题意；最高位为 0 的串只是数值较小的数的“带前导零写法”，被 printNumber 归一化了。

复杂度分析

枚举数量：递归枚举 10^n 个组合（含前导零写法），即时间复杂度 O(10^n)，其中每个组合打印需扫描 O(n) 个字符，整体输出量本身就是 10^n 量级，无法再优化——这是一个“输出敏感型”问题的下界；
递归深度：O(n)，对应调用栈深度；
额外空间：除栈外只有 O(n) 的 char[]。

这里 n 是位数而不是数值大小，所以即便 n 大到 1000，存储也只需 1000 个字符——这正是选择 char 数组而非整型的根本收益。当然输出 10^1000 个数在工程上不可能完成，题目的真正考点是**“用定长字符数组 + 回溯枚举处理任意长度数字”的方法论**，而不是真的要跑完 n = 1000。

与仓库内其他题目的关系

这道题在 [notes/剑指 Offer 题解 - 目录.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files) 中被归入“其它”分类，它与以下题目构成知识簇：

[notes/12. 矩阵中的路径.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/12. 矩阵中的路径.md?utm_source=gitcode_repo_files)：仓库中对回溯法（backtracking）的总述出处，给出“搜索所有可能结果 + 回溯清除状态”的标准定义；本题可视为其在一维定长序列上的特例（无 visited 标记，覆盖式写值）；
[notes/38. 字符串的排列.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/38. 字符串的排列.md?utm_source=gitcode_repo_files)：同模板的回溯题，区别在于使用 hasUsed[] 标记与显式撤销，且需要剪枝去重；
[notes/44. 数字序列中的某一位数字.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/44. 数字序列中的某一位数字.md?utm_source=gitcode_repo_files)：同样处理“把数字序列化为字符”的问题，但方向相反——第 44 题不枚举，而是用位数分组（10、90、900...）做数学定位，O(log index) 直接取出第 index 位数字；两题放在一起可以对比“全枚举 vs 数学定位”两种处理大数字串的思路。