Kiểm tra số lớn chia thành các đoạn bằng tổng C++

Cho số dưới dạng string. Kiểm tra có thể chia thành ≥2 đoạn liên tiếp có tổng chữ số bằng nhau không.

Ví dụ: "74325" → (7), (4,3), (2,5) đều có tổng = 7.

Giải thuật

1. Tính mảng prefix_sum
2. Thử mỗi vị trí i làm điểm kết thúc đoạn đầu (tổng = prefix_sum[i-1])
3. Duyệt tiếp: cộng dồn chữ số, nếu bằng tổng đoạn đầu → reset, tiếp tục đoạn mới
4. Nếu vượt tổng → break, thử i tiếp theo
5. Kết thúc chuỗi và tổng đoạn cuối = 0 → thành công

Ví dụ minh họa

#include <iostream>
#include <string>
using namespace std;

bool canBeSegmented(string str) {
    int n = str.length();
    int prefix_sum[n];
    prefix_sum[0] = str[0] - '0';
    for (int i = 1; i < n; i++)
        prefix_sum[i] = prefix_sum[i-1] + (str[i] - '0');
    
    for (int i = 1; i <= n - 1; i++) {
        int target = prefix_sum[i - 1];
        int currSum = 0;
        int it = i;
        bool found = false;
        
        while (it < n) {
            currSum += str[it] - '0';
            if (currSum == target) { currSum = 0; found = true; }
            else if (currSum > target) break;
            it++;
        }
        if (currSum == 0 && it == n && found) return true;
    }
    return false;
}

int main() {
    string s = "74325";
    cout << (canBeSegmented(s) ? "Co the chia thanh cac doan bang tong" : "Khong the chia");
}

Kết quả

Co the chia thanh cac doan bang tong