C++ 打印所有 n 位數：遞歸與字符串兩種實現詳解

「打印 1 到最大的 n 位數」是經典面試題（劍指 Offer 題 17）。本質是生成所有長度為 n 的十進制字符串（允許前導零），並去除前導零後輸出。本文詳細對比數組遞歸法與字符串模擬加法法兩種核心思路，並給出可直接運行的完整代碼。

一、問題澄清

• 輸入：整數 n (1 ≤ n ≤ 9，避免溢出)
• 輸出：從 1 到 10ⁿ−1 的所有整數，每行一個
• 核心難點：n 較大時無法用整型變量直接存儲，必須用字符串/數組模擬大數。

二、方法一：數組遞歸（全排列思想）

將 n 個位置視為 n 個槽，每個槽填 0~9，遞歸枚舉所有組合，最後去除前導零打印。

核心邏輯

void dfs(int* num, int n, int index) {
    if (index == n) {           // 填滿 n 位
        printNumber(num, n);    // 去除前導零輸出
        return;
    }
    for (int i = 0; i <= 9; ++i) {
        num[index] = i;
        dfs(num, n, index + 1);
    }
}

完整代碼

#include <iostream>
#include <cstring>
using namespace std;

void printNumber(int* num, int n) {
    int i = 0;
    while (i < n && num[i] == 0) ++i;  // 跳過前導零
    if (i == n) return;                // 全零不打印（即 0）
    for (; i < n; ++i) cout << num[i];
    cout << '\n';
}

void dfs(int* num, int n, int index) {
    if (index == n) {
        printNumber(num, n);
        return;
    }
    for (int i = 0; i <= 9; ++i) {
        num[index] = i;
        dfs(num, n, index + 1);
    }
}

void print1ToMaxOfNDigits(int n) {
    if (n <= 0) return;
    int* num = new int[n];
    memset(num, 0, n * sizeof(int));
    dfs(num, n, 0);
    delete[] num;
}

int main() {
    print1ToMaxOfNDigits(3);  // 打印 1~999
    return 0;
}

特點分析

• 優點：思路直觀，代碼簡潔，易於理解遞歸回溯。
• 缺點：遞歸深度 = n，調用棧開銷大；生成順序為字典序（000, 001, 002…），非數值序，但去除前導零後等效。
• 適用場景：n ≤ 6 時極快；n > 9 會棧溢出或輸出量爆炸（10⁹ 行）。

三、方法二：字符串模擬加法（大數加 1）

維護一個長度為 n 的字符數組初始化為全 '0'，反覆執行 +1 操作，直到最高位產生進位溢出為止。

核心邏輯：字符串加 1

// 返回 true 表示溢出（已達最大 n 位數），false 表示繼續
bool increment(char* num, int n) {
    int carry = 1;
    for (int i = n - 1; i >= 0; --i) {
        int sum = num[i] - '0' + carry;
        num[i] = '0' + (sum % 10);
        carry = sum / 10;
    }
    return carry == 1;  // 最高位仍有進位 → 溢出
}

完整代碼

#include <iostream>
#include <cstring>
using namespace std;

void printNumber(const char* num, int n) {
    int i = 0;
    while (i < n && num[i] == '0') ++i;
    if (i == n) return;
    for (; i < n; ++i) cout << num[i];
    cout << '\n';
}

bool increment(char* num, int n) {
    int carry = 1;
    for (int i = n - 1; i >= 0; --i) {
        int sum = num[i] - '0' + carry;
        num[i] = '0' + (sum % 10);
        carry = sum / 10;
    }
    return carry == 1;
}

void print1ToMaxOfNDigits_2(int n) {
    if (n <= 0) return;
    char* num = new char[n + 1];
    memset(num, '0', n);
    num[n] = '\0';
    
    while (true) {
        printNumber(num, n);
        if (increment(num, n)) break;  // 溢出結束
    }
    delete[] num;
}

int main() {
    print1ToMaxOfNDigits_2(2);  // 打印 1~99
    return 0;
}

特點分析

• 優點：無遞歸，內存佔用固定，生成順序為嚴格數值遞增序。
• 缺點：每次 +1 可能觸發連鎖進位，平均時間複雜度仍為 O(10ⁿ)，常數因子略大於遞歸法。
• 適用場景：n 較大時避免棧溢出；需嚴格按數值序輸出時。

四、兩方法深度對比

五、進階優化與變體

1. 非遞歸全排列：用 next_permutation 或手寫迭代版避免棧溢出。
2. 分段輸出/文件寫入：n ≥ 7 時輸出量巨大，建議用 ofstream 緩衝寫入文件而非 cout。
3. 多線程並行：將範圍劃分給多線程（如線程 1 處理 1~10ⁿ⁻¹，線程 2 處理 10ⁿ⁻¹~2×10ⁿ⁻¹），需線程安全輸出。
4. LeetCode 變體：printNumbers(n) 返回 vector<int>，n ≤ 9 時可直接用 int 存儲，無需大數模擬。

六、總結

「打印 1 到最大 n 位數」考察的核心是大數表示與操作。遞歸法勝在思路清晰、代碼短，適合面試現場白板寫代碼；字符串加法法勝在無遞歸風險、輸出順序天然正確，適合工程落地。實際工作中，n > 6 幾乎不會要求全量打印（輸出量 GB 級），更多是考察大數加法、乘法模擬能力。掌握兩種思路，舉一反三，才是這道題的真正價值。