Google 競賽題 SecretSum C++ 解法詳解：字母數字謎的組合計數

SecretSum 是 Google 競賽第二輪淘汰賽 500 分題目。給定三個由大寫字母組成的 3 字符串 num1、num2、result，每個字母代表唯一數字（0-9），同字母同數字，不同字母不同數字，且最高位字母不能為 0。求滿足 num1 + num2 = result 的合法數字映射總數。

題目形式化

• 輸入：三個長度為 3 的大寫字母串；
• 輸出：滿足條件的映射方案數（int）；
• 約束：最多 10 個不同字母（A-J），可用全排列暴力搜尋；
• 前導零限制：每個串的首字母對應數字 ≠ 0。

解法思路：回溯 + 剪枝

1. 收集所有出現的不同字母，建立字母→索引映射；
2. 記錄哪些字母是「首字母」（不可為 0）；
3. 對 10 個數字進行全排列，選取前 k 個分配給 k 個字母；
4. 檢查首字母非零約束；
5. 將三個串轉為對應整數，驗證等式；
6. 計數合法方案。

核心 C++ 實現

#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

class SecretSum {
public:
    int countPossible(std::string num1, std::string num2, std::string result) {
        // 1. 收集唯一字母
        std::string all = num1 + num2 + result;
        std::sort(all.begin(), all.end());
        all.erase(std::unique(all.begin(), all.end()), all.end());
        int n = all.size();
        if (n > 10) return 0;  // 超過 10 個不同字母不可能

        // 2. 字母→索引映射
        std::unordered_map<char, int> idx;
        for (int i = 0; i < n; ++i) idx[all[i]] = i;

        // 3. 標記首字母
        std::vector<bool> isLeading(10, false);
        isLeading[idx[num1[0]]] = true;
        isLeading[idx[num2[0]]] = true;
        isLeading[idx[result[0]]] = true;

        // 4. 數字陣列 0-9
        std::vector<int> digits(10);
        std::iota(digits.begin(), digits.end(), 0);

        int count = 0;
        // 5. 全排列枚舉
        do {
            // 檢查首字母非零
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                if (isLeading[i] && digits[i] == 0) { ok = false; break; }
            }
            if (!ok) continue;

            // 轉換字符串為數值
            auto toVal = [&](const std::string& s) {
                int val = 0;
                for (char c : s) val = val * 10 + digits[idx[c]];
                return val;
            };

            if (toVal(num1) + toVal(num2) == toVal(result))
                ++count;
        } while (std::next_permutation(digits.begin(), digits.end()));

        return count;
    }
};

範例驗證

複雜度分析

• 時間：O(10! / (10-n)!) * n，n ≤ 10，最壞 ~360 萬次迭代，極快；
• 空間：O(1)。

優化方向（可選）

• 列式加法逐位約束（如個位：C1+C2 ≡ R1 (mod 10)），提前剪枝；
• 使用位掩碼代替 vector<int> 加速排列生成；
• 若字母數固定為 10，可直接 do { ... } while(next_permutation) 無需切片。

本題核心在於將「字母唯一映射數字」轉化為「數字全排列分配給字母」，利用 STL next_permutation 簡潔實現完整搜索，是典型的「暴力可行」競賽題範例。