Split the array into equal sum parts according to given conditions in C++

Here we will see one problem. Suppose one array arr is given. We have to check whether the array can be split into two parts, such that −

• Sub of both sub-arrays will be the same
• All elements, which are multiple of 5, will be in the same group
• All elements which are multiple of 3, but not multiple of 5, will be in the same group
• All other elements will be in other groups.

Suppose the array elements are {1, 4, 3}, then this can be split, because the sum of {1, 3} is the same as the sum of {4}, and the groups are also correct for the given condition.

Algorithm

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

Example

 Live Demo

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

Output

Can be split