แยกอาร์เรย์ออกเป็นส่วนผลรวมเท่ากันตามเงื่อนไขที่กำหนดใน C++

ที่นี่เราจะเห็นปัญหาหนึ่ง สมมติว่ามี arr หนึ่งอาร์เรย์ เราต้องตรวจสอบว่าอาร์เรย์สามารถแบ่งออกเป็นสองส่วนได้หรือไม่ −

• Sub ของอาร์เรย์ย่อยทั้งสองจะเหมือนกัน
• อิลิเมนต์ทั้งหมด ซึ่งคูณด้วย 5 จะอยู่ในกลุ่มเดียวกัน
• องค์ประกอบทั้งหมดที่มีผลคูณ 3 แต่ไม่คูณ 5 จะอยู่ในกลุ่มเดียวกัน
• องค์ประกอบอื่นๆ ทั้งหมดจะอยู่ในกลุ่มอื่น

สมมติว่าองค์ประกอบอาร์เรย์คือ {1, 4, 3} ค่านี้สามารถแยกออกได้ เนื่องจากผลรวมของ {1, 3} เท่ากับผลรวมของ {4} และกลุ่มก็ถูกต้องตามเงื่อนไขที่กำหนด

อัลกอริทึม

isSplitArray(arr, n, start, left_sum, right_sum) -

Begin
   if start = n, then return true when left_sum = right_sum, otherwise false
   if arr[start] is divisible by 5, then add arr[start] with the left_sum
   else if arr[start] is divisible by 3, then add arr[start] with the right_sum
   else
      return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start])
   isSplitArray(arr, n, start + 1, left_sum, right_sum)
End

ตัวอย่าง

#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
   if (start == n) //when it reaches at the end
      return left_sum == right_sum;
   if (arr[start] % 5 == 0) //when the element is divisible by 5, add to left sum
      left_sum += arr[start];
   else if (arr[start] % 3 == 0) //when the element is divisible by 3 but not 5, add to right sum
         right_sum += arr[start];
   else // otherwise it can be added to any of the sub-arrays
         return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
   // For cases when element is multiple of 3 or 5.
   return isSplitArray(arr, n, start + 1, left_sum, right_sum);
}
int main() {
   int arr[] = {1, 4, 3};
   int n = sizeof(arr)/sizeof(arr[0]);
   if(isSplitArray(arr, n, 0, 0, 0)){
      cout <<"Can be split";
   } else {
      cout <<"Can not be split";
   }
}

ผลลัพธ์

Can be split