Chương trình C++ kiểm tra mảng có chia được thành 2 mảng con tổng bằng nhau

Cho mảng A. Kiểm tra có tách thành 2 phần có tổng bằng nhau không. Ví dụ [6,1,3,2,5] → [6,1] và [2,5].

Giải pháp: tính tổng tất cả phần tử. Với mỗi phần tử, tính tổng bên phải = tổng_all - tổng_đến_hiện_tại.

Ví dụ mã nguồn

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

void displaySubArray(int arr[], int left, int right) {
    cout << "[ ";
    for (int i = left; i <= right; i++)
        cout << arr[i] << " ";
    cout << "] ";
}

void subarrayOfSameSum(int arr[], int n) {
    int total_sum = accumulate(arr, arr+n, 0);
    int so_far_sum = 0;
    for (int i = 0; i < n; i++) {
        if (2*so_far_sum + arr[i] == total_sum) {
            cout << "subarray 1: "; displaySubArray(arr, 0, i-1);
            cout << "\nsubarray 2: "; displaySubArray(arr, i+1, n-1);
            return;
        }
        so_far_sum += arr[i];
    }
    cout << "No subarray can be formed";
}

int main() {
    int arr[] = {6, 1, 3, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    subarrayOfSameSum(arr, n);
}

Kết quả đầu ra

subarray 1: [ 6 1 ]
subarray 2: [ 2 5 ]