ค้นหาว่าอาร์เรย์สามารถแบ่งออกเป็นสองอาร์เรย์ย่อยของผลรวมเท่ากันใน 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 ]