ตัวเลขบวกกันได้ (Additive Number) ใน C++

ให้สตริงตัวเลข ตรวจสอบว่าเป็น Additive Number หรือไม่ คือ สามารถแบ่งเป็นลำดับอย่างน้อย 3 ตัวที่ตัวหลัง = ผลรวมสองตัวก่อนหน้า (เช่น ฟิบอนัชชี)

ตัวอย่าง: "112358" → true (1,1,2,3,5,8 : 2=1+1, 3=1+2, 5=2+3, 8=3+5)

ขั้นตอนการแก้ปัญหา (Backtracking)

1. ลองทุกความเป็นไปได้ของสองตัวแรก:
   • i = ความยาวรวมของสองตัวแรก (1 ถึง n-2)
   • j = ความยาวของตัวแรก (1 ถึง i)
   • s1 = num[0..j-1], s2 = num[j..i]
   • ข้ามถ้า leading zero (เช่น "01")
2. ฟังก์ชัน ok(s, idx, prev1, prev2):
   • ถ้า = s.size() → true
   • req = prev1 + prev2, แปลงเป็นสตริง num
   • สร้าง x จาก s[idx...] ทีละตัว ถ้า เรียก ok(s, idx+len, prev2, req)
   • ไม่เจอ → false
3. ถ้าหนึ่งคู่ทำได้ → true, ไม่ได้ทั้งหมด → false

ตัวอย่างโค้ด C++

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

class Solution {
public:
    bool ok(string s, int idx, lli prev1, lli prev2) {
        if (idx >= s.size()) return true;
        lli req = prev1 + prev2;
        string num = to_string(req);
        string x = "";
        for (int i = idx; i < s.size(); i++) {
            x += s[i];
            if (x == num && ok(s, i + 1, prev2, stoll(x))) return true;
        }
        return false;
    }
    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);
                int mx = max(s1.size(), s2.size());
                if (mx > n - i) continue;
                if ((s1[0]=='0' && s1.size()>1) || (s2[0]=='0' && s2.size()>1)) continue;
                if (ok(num, i + 1, stoll(s1), stoll(s2))) return true;
            }
        }
        return false;
    }
};

int main() {
    Solution ob;
    cout << ob.isAdditiveNumber("112358");
}

Input

"112358"

Output

1