Chia mảng thành các phần có tổng bằng nhau theo các điều kiện đã cho trong C ++

Ở đây chúng ta sẽ thấy một vấn đề. Giả sử một mảng arr được cho trước. Chúng ta phải kiểm tra xem mảng có thể được chia thành hai phần hay không, sao cho -

• Con của cả hai mảng con sẽ giống nhau
• Tất cả các phần tử, là bội số của 5, sẽ ở cùng một nhóm
• Tất cả các phần tử là bội số của 3, nhưng không phải bội số của 5, sẽ ở cùng một nhóm
• Tất cả các phần tử khác sẽ nằm trong các nhóm khác.

Giả sử các phần tử của mảng là {1, 4, 3}, thì điều này có thể được tách, vì tổng của {1, 3} giống với tổng của {4} và các nhóm cũng đúng với điều kiện đã cho.

Thuật toán

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

Ví dụ

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

Đầu ra

Can be split