Partition a set into two subsets such that the difference of subset sums is minimum | A Recursive Python3 program to solve minimum sum partition problem . ; Returns the minimum value of the difference of the two sets . ; Calculate sum of all elements ; Create an 2d list to store results of subproblems ; Initialize first column as true . 0 sum is possible with all elements . ; Initialize top row , except dp [ 0 ] [ 0 ] , as false . With 0 elements , no other sum except 0 is possible ; Fill the partition table in bottom up manner ; If i 'th element is excluded ; If i 'th element is included ; Initialize difference of two sums . ; Find the largest j such that dp [ n ] [ j ] is true where j loops from sum / 2 t0 0 ; Driver code
import sys NEW_LINE def findMin ( a , n ) : NEW_LINE INDENT su = 0 NEW_LINE su = sum ( a ) NEW_LINE dp = [ [ 0 for i in range ( su + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = True NEW_LINE DEDENT for j in range ( 1 , su + 1 ) : NEW_LINE INDENT dp [ 0 ] [ j ] = False NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , su + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE if a [ i - 1 ] <= j : NEW_LINE INDENT dp [ i ] [ j ] |= dp [ i - 1 ] [ j - a [ i - 1 ] ] NEW_LINE DEDENT DEDENT DEDENT diff = sys . maxsize NEW_LINE for j in range ( su // 2 , - 1 , - 1 ) : NEW_LINE INDENT if dp [ n ] [ j ] == True : NEW_LINE INDENT diff = su - ( 2 * j ) NEW_LINE break NEW_LINE DEDENT DEDENT return diff NEW_LINE DEDENT a = [ 3 , 1 , 4 , 2 , 2 , 1 ] NEW_LINE n = len ( a ) NEW_LINE print ( " The ▁ minimum ▁ difference ▁ between ▁ " "2 ▁ sets ▁ is ▁ " , findMin ( a , n ) ) NEW_LINE