Description

Submission

class Solution {
    using ll = unsigned long long;
    bool dfs(string& num, int idx, pair<ll, ll> prev, int level) {
        if(idx >= num.length()) {
            if(prev.first != -1 && level > 2) return true;
            return false;
        }
        
        if(prev.first == -1) {
            for(int i = 1; i < 18; ++i) {
                string cur = num.substr(idx, i);
                if(cur.size() > 1 && cur[0] == '0') break;
                if(dfs(num, idx + i, {prev.second, stoll(cur)}, level + 1)) {
                    return true;
                }
            }
            return false;
        }

        long long t = prev.first + prev.second;
        string s = to_string(t);
        string cur = num.substr(idx, s.length());
        if(cur.length() > 1 && cur[0] == 0) return false;
        if(cur == s && dfs(num, idx + s.length(), {prev.second, stoll(cur)}, level + 1)) return true;

        return false;
    }
public:
    bool isAdditiveNumber(string num) {
        return dfs(num, 0, {-1, -1}, 0);
    }
};