algo-aha

数字串分割成fibonacci数列

• https://leetcode.com/problems/additive-number/

只要前两个确定，整个分割也都确定了

bool isAdditiveNumber(string num) {
    // 选头两个数字长为i和j
    const int N = num.size();
    for (int i = 1; i <= N / 2; i++) {
        if (i > 1 && num[0] == '0') break;
        for (int j = 1; j <= (N - i) / 2; j++) {
            if (j > 1 && num[i] == '0') break;
            if (isValid(num, i + j, num.substr(0, i), num.substr(i, j))) return true;
        }
    }
    return false;
}

// num[idx..]开头是不是等于n1+n2
bool isValid(const string &num, int idx, const string &n1, const string &n2) {
    const int N = num.size();
    if (idx == N) return true;
    auto sum = add(n1, n2); 
    int len = sum.size();
    if (idx + len > N || num.substr(idx, len) != sum) return false;
    return isValid(num, idx + len, n2, sum);
}

// 数字串加法可解决超大数溢出问题
string add(const string &a, const string &b) {
    // return to_string(stoll(a) + stoll(b));
    string ans;
    int carry = 0;
    int i = (int)a.size() - 1, j = (int)b.size() - 1;
    while (i >= 0 || j >= 0 || carry > 0) {
        if (i >= 0) carry += a[i--] - '0';
        if (j >= 0) carry += b[j--] - '0';
        ans.push_back(carry % 10 + '0');
        carry /= 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

• https://leetcode.com/problems/split-array-into-fibonacci-sequence/

返回所有分割，回溯法

vector<int> splitIntoFibonacci(string S) {
    vector<int> ans;
    search(S, 0, ans);
    return ans;
}

bool search(const string &s, int idx, vector<int> &ans) {
    const int N = s.size(), M = ans.size();
    if (idx == N && M >= 3) return true;
    
    // s[idx..i]分割出数num
    for (int i = idx; i < N; i++) {
        if (i > idx && s[idx] == '0') continue; // 多位数的首位不能为0
        int len = i - idx + 1;
        if (len > 10) continue; // < 2^31, 最多10位数
        long num = stol(s.substr(idx, len));
        if (num > INT_MAX) continue; // 太大溢出
        if (M >= 2 && ans[M-2] + ans[M-1] != num) continue; // 不满足Fibonacci性质
        ans.push_back(num);
        if (search(s, i + 1, ans)) return true;
        ans.pop_back();
    }
    return false;
}