Giả sử chúng ta có một mảng A. Chúng ta phải kiểm tra xem chúng ta có thể chia mảng thành hai phần mà tổng của chúng bằng nhau hay không. Giả sử các phần tử là [6, 1, 3, 2, 5], thì [6, 1] và [2, 5] có thể là hai mảng con.
Vấn đề này có thể được giải quyết dễ dàng bằng cách làm theo các quy tắc này. Lúc đầu, chúng ta phải tìm tổng của tất cả các phần tử của mảng, sau đó đối với mỗi phần tử của mảng, chúng ta có thể tính tổng đúng bằng cách sử dụng total_sum - tổng các phần tử được tìm thấy cho đến nay.
Ví dụ
#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);
} Đầu ra
subarray 1: [ 6 1 ] subarray 2: [ 2 5 ]