C ++で指定された条件に従って、配列を等しい合計部分に分割します

ここで1つの問題が発生します。 1つの配列arrが指定されているとします。 -

• 両方のサブアレイのサブは同じになります
• 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