Split array into two equal length subsets such that all repetitions of a number lies in a single subset | Python3 program for the above approach ; Function to create the frequency array of the given array arr [ ] ; Hashmap to store the frequencies ; Store freq for each element ; Get the total frequencies ; Store frequencies in subset [ ] array ; Return frequency array ; Function to check is sum N / 2 can be formed using some subset ; dp [ i ] [ j ] store the answer to form sum j using 1 st i elements ; Initialize dp [ ] [ ] with true ; Fill the subset table in the bottom up manner ; If current element is less than j ; Update current state ; Return the result ; Function to check if the given array can be split into required sets ; Store frequencies of arr [ ] ; If size of arr [ ] is odd then print " Yes " ; Check if answer is true or not ; Print the result ; Driver Code ; Given array arr ; Function Call
from collections import defaultdict NEW_LINE def findSubsets ( arr ) : NEW_LINE INDENT M = defaultdict ( int ) NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT M [ arr [ i ] ] += 1 NEW_LINE DEDENT subsets = [ 0 ] * len ( M ) NEW_LINE i = 0 NEW_LINE for j in M : NEW_LINE INDENT subsets [ i ] = M [ j ] NEW_LINE i += 1 NEW_LINE DEDENT return subsets NEW_LINE DEDENT def subsetSum ( subsets , target ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( target + 1 ) ] for y in range ( len ( subsets ) + 1 ) ] NEW_LINE for i in range ( len ( dp ) ) : NEW_LINE INDENT dp [ i ] [ 0 ] = True NEW_LINE DEDENT for i in range ( 1 , len ( subsets ) + 1 ) : NEW_LINE INDENT for j in range ( 1 , target + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE if ( j >= subsets [ i - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] |= ( dp [ i - 1 ] [ j - subsets [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ len ( subsets ) ] [ target ] NEW_LINE DEDENT def divideInto2Subset ( arr ) : NEW_LINE INDENT subsets = findSubsets ( arr ) NEW_LINE if ( len ( arr ) % 2 == 1 ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT isPossible = subsetSum ( subsets , len ( arr ) // 2 ) NEW_LINE if ( isPossible ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 1 , 2 , 3 ] NEW_LINE divideInto2Subset ( arr ) NEW_LINE DEDENT