程式語言 - LeetCode - C++ - 306. Additive Number


參考資訊：
https://www.cnblogs.com/grandyang/p/4974115.html

題目：


解答： 

class Solution {
public:
    bool isAdditiveNumber(string num) {
        auto add = [](string a, string b) {
            string res;
            int carry = 0;
            int i = a.size() - 1;
            int j = b.size() - 1;

            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(sum % 10 + '0');
                carry = sum / 10;
            }

            reverse(res.begin(), res.end());
            return res;
        };

        auto dfs = [&](this auto&& dfs, string n, string n1, string n2) -> bool {
            if ((n1.size() > 1 && n1[0] == '0') || (n2.size() > 1 && n2[0] == '0')) {
                return false;
            }

            string sum = add(n1, n2);

            if (n == sum) {
                return true;
            }

            if (sum.size() > n.size() || n.substr(0, sum.size()) != sum) {
                return false;
            }

            return dfs(n.substr(sum.size()), n2, sum);
        };

        for (int i = 1; i < num.size(); ++i) {
            string s1 = num.substr(0, i);

            if (s1.size() > 1 && s1[0] == '0') break;

            for (int j = i + 1; j < num.size(); ++j) {
                string s2 = num.substr(i, j - i);

                if (s2.size() > 1 && s2[0] == '0') break;

                if (dfs(num.substr(j), s1, s2)) {
                    return true;
                }
            }
        }

        return false;
    }
};