Print equal sum sets of array ( Partition Problem ) | Set 2 | Python3 program to print equal sum sets of array . ; Function to print equal sum sets of array . ; Finding sum of array elements ; Check sum is even or odd . If odd then array cannot be partitioned . Print - 1 and return . ; Divide sum by 2 to find sum of two possible subsets . ; Boolean DP table to store result of states . dp [ i ] [ j ] = true if there is a subset of elements in first i elements of array that has sum equal to j . ; If number of elements are zero , then no sum can be obtained . ; Sum 0 can be obtained by not selecting any element . ; Fill the DP table in bottom up manner . ; Excluding current element . ; Including current element ; Required sets set1 and set2 . ; If partition is not possible print - 1 and return . ; Start from last element in dp table . ; If current element does not contribute to k , then it belongs to set 2. ; If current element contribute to k then it belongs to set 1. ; Print elements of both the sets . ; Driver Code
import numpy as np NEW_LINE def printEqualSumSets ( arr , n ) : NEW_LINE INDENT sum_array = sum ( arr ) NEW_LINE if ( sum_array & 1 ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE return NEW_LINE DEDENT k = sum_array >> 1 NEW_LINE dp = np . zeros ( ( n + 1 , k + 1 ) ) NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = False NEW_LINE DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for currSum in range ( 1 , k + 1 ) : NEW_LINE INDENT dp [ i ] [ currSum ] = dp [ i - 1 ] [ currSum ] NEW_LINE if ( arr [ i - 1 ] <= currSum ) : NEW_LINE INDENT dp [ i ] [ currSum ] = ( dp [ i ] [ currSum ] or dp [ i - 1 ] [ currSum - arr [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT set1 , set2 = [ ] , [ ] NEW_LINE if ( not dp [ n ] [ k ] ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE return NEW_LINE DEDENT i = n NEW_LINE currSum = k NEW_LINE while ( i > 0 and currSum >= 0 ) : NEW_LINE INDENT if ( dp [ i - 1 ] [ currSum ] ) : NEW_LINE INDENT i -= 1 NEW_LINE set2 . append ( arr [ i ] ) NEW_LINE DEDENT elif ( dp [ i - 1 ] [ currSum - arr [ i - 1 ] ] ) : NEW_LINE INDENT i -= 1 NEW_LINE currSum -= arr [ i ] NEW_LINE set1 . append ( arr [ i ] ) NEW_LINE DEDENT DEDENT print ( " Set ▁ 1 ▁ elements : " , end = " ▁ " ) NEW_LINE for i in range ( len ( set1 ) ) : NEW_LINE INDENT print ( set1 [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( " Set 2 elements : " , ▁ end ▁ = ▁ "   " ) NEW_LINE for i in range ( len ( set2 ) ) : NEW_LINE INDENT print ( set2 [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 5 , 1 , 11 ] NEW_LINE n = len ( arr ) NEW_LINE printEqualSumSets ( arr , n ) NEW_LINE DEDENT