Number of ways to divide an array into K equal sum sub | C ++ implementation of the approach ; Array to store the states of DP ; Array to check if a state has been solved before ; To store the sum of the array elements ; Function to find the sum of all the array elements ; Function to return the number of ways ; If sum is not divisible by k answer will be zero ; Base case ; To check if a state has been solved before ; Sum of all the numbers from the beginning of the array ; Setting the current state as solved ; Recurrence relation ; Returning solved state ; Driver code ; Function call to find the sum of the array elements ; Print the number of ways
#include <bits/stdc++.h> NEW_LINE #define max_size  20 NEW_LINE #define max_k  20 NEW_LINE using namespace std ; int dp [ max_size ] [ max_k ] ; bool v [ max_size ] [ max_k ] ; int sum = 0 ; void findSum ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; } int cntWays ( int arr [ ] , int i , int ck , int k , int n , int curr_sum ) { if ( sum % k != 0 ) return 0 ; if ( i != n and ck == k + 1 ) return 0 ; if ( i == n ) { if ( ck == k + 1 ) return 1 ; else return 0 ; } if ( v [ i ] [ ck ] ) return dp [ i ] [ ck ] ; curr_sum += arr [ i ] ; v [ i ] [ ck ] = 1 ; dp [ i ] [ ck ] = cntWays ( arr , i + 1 , ck , k , n , curr_sum ) ; if ( curr_sum == ( sum / k ) * ck ) dp [ i ] [ ck ] += cntWays ( arr , i + 1 , ck + 1 , k , n , curr_sum ) ; return dp [ i ] [ ck ] ; } int main ( ) { int arr [ ] = { 1 , -1 , 1 , -1 , 1 , -1 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 2 ; findSum ( arr , n ) ; cout << cntWays ( arr , 0 , 1 , k , n , 0 ) ; }