Number of times an array can be partitioned repetitively into two subarrays with equal sum | C ++ program for the above approach ; Recursion Function to calculate the possible splitting ; If there are less than two elements , we cannot partition the sub - array . ; Iterate from the start to end - 1. ; Recursive call to the left and the right sub - array . ; If there is no such partition , then return 0 ; Function to find the total splitting ; Prefix array to store the prefix - sum using 1 based indexing ; Store the prefix - sum ; Function Call to count the number of splitting ; Driver Code ; Given array ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int splitArray ( int start , int end , int * arr , int * prefix_sum ) { if ( start >= end ) return 0 ; for ( int k = start ; k < end ; ++ k ) { if ( ( prefix_sum [ k ] - prefix_sum [ start - 1 ] ) == ( prefix_sum [ end ] - prefix_sum [ k ] ) ) { return 1 + splitArray ( start , k , arr , prefix_sum ) + splitArray ( k + 1 , end , arr , prefix_sum ) ; } } return 0 ; } void solve ( int arr [ ] , int n ) { int prefix_sum [ n + 1 ] ; prefix_sum [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { prefix_sum [ i ] = prefix_sum [ i - 1 ] + arr [ i - 1 ] ; } cout << splitArray ( 1 , n , arr , prefix_sum ) ; } int main ( ) { int arr [ ] = { 12 , 3 , 3 , 0 , 3 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; solve ( arr , N ) ; return 0 ; }