306.累加数

链接：306.累加数
难度：Medium
标签：字符串、回溯
简介：给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

题解 1 - cpp

• 编辑时间：2022-01-10
• 执行用时：4ms
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    bool isAdditiveNumber(string num) {
        string prev1 = "", prev2 = "";
        for (int end1 = 0; end1 < num.size(); end1++) {
            prev1 += num[end1];
            prev2 = "";
            for (int end2 = end1 + 1; end2 < num.size(); end2++) {
                prev2 += num[end2];
                if (dfs(num, end2 + 1, 1, prev1, prev2)) return 1;
                if (end2 == end1 + 1 && num[end2] == '0') break;
            }
            if (end1 == 0 && num[end1] == '0') break;
        }
        return 0;
    }
    string add(string s1, string s2) {
        string ans = "";
        int i1 = s1.size() - 1, i2 = s2.size() - 1, tag = 0;
        while (i1 >= 0 || i2 >= 0) {
            int num = (i1 < 0 ? 0 : s1[i1--] - '0') +
                      (i2 < 0 ? 0 : s2[i2--] - '0') + tag;
            if (num >= 10) {
                num -= 10;
                tag = 1;
            } else
                tag = 0;
            ans = to_string(num) + ans;
        }
        if (tag) ans = "1" + ans;
        return ans;
    }
    int dfs(string& num, int start, int init, string prev1, string prev2) {
        if (start == num.size()) return !init;
        string next = "";
        for (int i = start; i < num.size(); i++) {
            next += num[i];
            if (next == add(prev1, prev2))
                return dfs(num, i + 1, 0, prev2, next);
            if (i == start && num[i] == '0') break;
        }
        return 0;
    }
};