โปรแกรม C++ ตรวจสอบว่าอาร์เรย์แบ่งเป็นสองซับอาร์เรย์ผลรวมเท่ากันได้หรือไม่

สมมติเรามีอาร์เรย์ A เราต้องตรวจสอบว่าเราสามารถแบ่งอาร์เรย์เป็นสองส่วนที่ผลรวมเท่ากันได้หรือไม่ สมมติสมาชิกคือ [6, 1, 3, 2, 5] แล้ว [6, 1] และ [2, 5] สามารถเป็นซับอาร์เรย์ได้

ปัญหานี้แก้ได้ง่ายโดยทำตามกฎเหล่านี้ เราต้องหาผลรวมของสมาชิกทั้งหมดของอาร์เรย์ก่อน แล้วสำหรับแต่ละสมาชิก เราสามารถคำนวณผลรวมด้านขวาโดยใช้ total_sum - ผลรวมของสมาชิกที่หามาแล้ว

ตัวอย่าง

#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); 
}

ผลลัพธ์

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