Number of ways to divide an array into K equal sum sub | Python3 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
import numpy as np NEW_LINE max_size = 20 NEW_LINE max_k = 20 NEW_LINE dp = np . zeros ( ( max_size , max_k ) ) ; NEW_LINE v = np . zeros ( ( max_size , max_k ) ) ; NEW_LINE sum = 0 ; NEW_LINE def findSum ( arr , n ) : NEW_LINE INDENT global sum NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] ; NEW_LINE DEDENT DEDENT def cntWays ( arr , i , ck , k , n , curr_sum ) : NEW_LINE INDENT if ( sum % k != 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( i != n and ck == k + 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( i == n ) : NEW_LINE INDENT if ( ck == k + 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT DEDENT if ( v [ i ] [ ck ] ) : NEW_LINE INDENT return dp [ i ] [ ck ] ; NEW_LINE DEDENT curr_sum += arr [ i ] ; NEW_LINE v [ i ] [ ck ] = 1 ; NEW_LINE dp [ i ] [ ck ] = cntWays ( arr , i + 1 , ck , k , n , curr_sum ) ; NEW_LINE if ( curr_sum == ( sum / k ) * ck ) : NEW_LINE INDENT dp [ i ] [ ck ] += cntWays ( arr , i + 1 , ck + 1 , k , n , curr_sum ) ; NEW_LINE DEDENT return dp [ i ] [ ck ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , - 1 , 1 , - 1 , 1 , - 1 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE k = 2 ; NEW_LINE findSum ( arr , n ) ; NEW_LINE print ( cntWays ( arr , 0 , 1 , k , n , 0 ) ) ; NEW_LINE DEDENT