LeetCode 306 累加數：DFS + 字符串大數加法完整解析

題目重述

給定一個僅包含數字的字符串，判斷能否拆分成至少三個數字構成的「累加序列」：除前兩個數外，每個數等於前兩數之和。數字不允許前導零（單個 0 除外）。

例子："112358" → 1,1,2,3,5,8 ✅；"199100199" → 1,99,100,199 ✅。

核心思路：枚舉前兩數 + DFS 驗證

序列完全由前兩個數決定。窮舉所有合法的前兩數切分點，然後遞歸驗證剩餘字符串是否匹配後續和值。

關鍵難點

1. 大數加法：輸入長度可達 35 位，超出 64 位整數範圍 → 必須用字符串模擬加法。
2. 前導零判斷：子串長度 > 1 且首字符為 '0' 直接非法。
3. 剪枝優化：第一個數最長 n-2，第二個數最長 n-i-1，且若首字符為 '0' 只能取長度 1。

算法詳解

1. 字符串大數加法

std::string addStrings(const std::string& a, const std::string& b) {
    std::string res;
    int i = a.size() - 1, j = b.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res.push_back('0' + (sum % 10));
        carry = sum / 10;
    }
    std::reverse(res.begin(), res.end());
    return res;
}

2. DFS 驗證函數

bool dfs(const std::string& remaining, const std::string& prev1, const std::string& prev2) {
    if (remaining.empty()) return true; // 全部匹配成功
    if (remaining[0] == '0') return false; // 剩餘以 0 開頭但非單個 0 → 非法
    
    std::string sum = addStrings(prev1, prev2);
    if (remaining.size() < sum.size()) return false; // 剩餘長度不足
    if (remaining.substr(0, sum.size()) != sum) return false; // 前綴不匹配
    
    // 匹配成功，遞歸驗證剩餘部分
    return dfs(remaining.substr(sum.size()), prev2, sum);
}

3. 主函數雙重循環枚舉

bool isAdditiveNumber(std::string num) {
    int n = num.size();
    if (n < 3) return false;
    
    for (int i = 1; i <= n - 2; ++i) {          // 第一個數長度
        if (i > 1 && num[0] == '0') break;      // 前導零剪枝
        std::string first = num.substr(0, i);
        
        for (int j = 1; j <= n - i - 1; ++j) {  // 第二個數長度
            if (j > 1 && num[i] == '0') break;  // 前導零剪枝
            std::string second = num.substr(i, j);
            
            if (dfs(num.substr(i + j), first, second))
                return true;
        }
    }
    return false;
}

複雜度分析

• 時間：O(n^3)。雙重循環 O(n^2)，每次 DFS 最深 O(n) 步，每步大數加法 O(n)。實際上剪枝極強，遠快於理論上界。
• 空間：O(n) 遞歸棧 + 字符串臨時空間。

測試用例

Follow-up：超大整數溢出處理

本解法通過字符串加法天然解決溢出問題，無需額外大數庫。若語言內置大數（Python/Java BigInteger），可直接用整數運算簡化代碼。

總結

「枚舉首兩數 + DFS 驗證」是解決累加數問題的標準範式。關鍵在於：

1. 正確處理字符串大數加法（逆序逐位相加 + 進位）
2. 嚴格前導零剪枝（長度>1且首字符為'0'直接返回）
3. 利用子串前綴匹配快速失敗

此題是「字符串處理 + 遞歸 + 大數運算」的優秀綜合訓練。