Số cộng dồn (Additive Number) trong C++

Mô tả bài toán

Cho chuỗi số. Xác định có phải số cộng dồn không: có thể tách thành dãy ≥3 số, từ số thứ 3 trở đi mỗi số = tổng 2 số trước. Không cho phép số dẫn đầu 0 (trừ số 0).

Ví dụ: "112358" → true (1,1,2,3,5,8: 2=1+1, 3=1+2, 5=2+3, 8=3+5).

Giải thuật Thử tất cả cặp số đầu (Backtracking)

1. Thử tất cả cặp số đầu s1, s2 (cắt chuỗi tại 2 vị trí).
2. Bỏ qua nếu có số dẫn đầu 0 (độ dài > 1).
3. Đệ quy kiểm tra: tính sum = s1 + s2, kiểm tra chuỗi còn lại có bắt đầu bằng sum không. Nếu có, tiếp tục với (s2, sum).
4. Nếu duyệt hết chuỗi → true.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

class Solution {
    bool check(string& s, int idx, lli a, lli b) {
        if (idx >= s.size()) return true;
        lli sum = a + b;
        string sumStr = to_string(sum);
        if (s.substr(idx, sumStr.size()) != sumStr) return false;
        return check(s, idx + sumStr.size(), b, sum);
    }
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j <= i; j++) {
                string s1 = num.substr(0, j);
                string s2 = num.substr(j, i - j + 1);
                if ((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;
                if (check(num, i + 1, stoll(s1), stoll(s2))) return true;
            }
        }
        return false;
    }
};

int main() {
    Solution ob;
    cout << ob.isAdditiveNumber("112358"); // 1 (true)
    return 0;
}

Độ phức tạp

• Thời gian: O(n^2 * log(maxVal)) (thử O(n^2) cặp đầu, mỗi lần kiểm tra O(n) với big integer).
• Không gian: O(n) stack đệ quy.