Number of ways to divide an array into K equal sum sub | Java 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
class GFG { static int max_size = 20 ; static int max_k = 20 ; static int [ ] [ ] dp = new int [ max_size ] [ max_k ] ; static boolean [ ] [ ] v = new boolean [ max_size ] [ max_k ] ; static int sum = 0 ; static void findSum ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; } static int cntWays ( int arr [ ] , int i , int ck , int k , int n , int curr_sum ) { if ( sum % k != 0 ) return 0 ; if ( i != n && 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 ] = true ; 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 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , - 1 , 1 , - 1 , 1 , - 1 } ; int n = arr . length ; int k = 2 ; findSum ( arr , n ) ; System . out . println ( cntWays ( arr , 0 , 1 , k , n , 0 ) ) ; } }