Partition of a set into K subsets with equal sum using BitMask and DP | Function to check whether K required partitions are possible or not ; Return true as the entire array is the answer ; If total number of partitions exceeds size of the array ; If the array sum is not divisible by K ; No such partitions are possible ; Required sum of each subset ; Initialize dp array with - 1 ; Sum of empty subset is zero ; Iterate over all subsets / masks ; If current mask is invalid , continue ; Iterate over all array elements ; Check if the current element can be added to the current subset / mask ; Transition ; Driver Code
def isKPartitionPossible ( arr , N , K ) : NEW_LINE INDENT if ( K == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( N < K ) : NEW_LINE INDENT return False NEW_LINE DEDENT sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT if ( sum % K != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT target = sum / K NEW_LINE dp = [ 0 for i in range ( 1 << 15 ) ] NEW_LINE for i in range ( ( 1 << N ) ) : NEW_LINE INDENT dp [ i ] = - 1 NEW_LINE DEDENT dp [ 0 ] = 0 NEW_LINE for mask in range ( ( 1 << N ) ) : NEW_LINE INDENT if ( dp [ mask ] == - 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( ( mask & ( 1 << i ) == 0 ) and dp [ mask ] + arr [ i ] <= target ) : NEW_LINE INDENT dp [ mask ( 1 << i ) ] = ( ( dp [ mask ] + arr [ i ] ) % target ) NEW_LINE DEDENT DEDENT DEDENT if ( dp [ ( 1 << N ) - 1 ] == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 1 , 4 , 5 , 3 , 3 ] NEW_LINE N = len ( arr ) NEW_LINE K = 3 NEW_LINE if ( isKPartitionPossible ( arr , N , K ) ) : NEW_LINE INDENT print ( " Partitions ▁ into ▁ equal ▁ " \ " sum ▁ is ▁ possible . " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Partitions ▁ into ▁ equal ▁ sum ▁ " \ " is ▁ not ▁ possible . " ) NEW_LINE DEDENT DEDENT