Minimize difference between sum of two K | Python3 program for the above approach ; Stores the values at recursive states ; Function to find the minimum difference between sum of two K - length subsets ; Base Case ; If k1 and k2 are 0 , then return the absolute difference between sum1 and sum2 ; Otherwise , return INT_MAX ; If the result is already computed , return the result ; Store the 3 options ; Including the element in first subset ; Including the element in second subset ; Not including the current element in both the subsets ; Store minimum of 3 values obtained ; Return the value for the current states ; Driver Code
import sys NEW_LINE dp = [ [ [ - 1 for i in range ( 100 ) ] for i in range ( 100 ) ] for i in range ( 100 ) ] NEW_LINE def minSumDifference ( arr , n , k1 , k2 , sum1 , sum2 ) : NEW_LINE INDENT global dp NEW_LINE if ( n < 0 ) : NEW_LINE INDENT if ( k1 == 0 and k2 == 0 ) : NEW_LINE INDENT return abs ( sum1 - sum2 ) NEW_LINE DEDENT else : NEW_LINE INDENT return sys . maxsize + 1 NEW_LINE DEDENT DEDENT if ( dp [ n ] [ sum1 ] [ sum2 ] != - 1 ) : NEW_LINE INDENT return dp [ n ] [ sum1 ] [ sum2 ] NEW_LINE DEDENT op1 = sys . maxsize + 1 NEW_LINE op2 = sys . maxsize + 1 NEW_LINE op3 = sys . maxsize + 1 NEW_LINE if ( k1 > 0 ) : NEW_LINE INDENT op1 = minSumDifference ( arr , n - 1 , k1 - 1 , k2 , sum1 + arr [ n ] , sum2 ) NEW_LINE DEDENT if ( k2 > 0 ) : NEW_LINE INDENT op2 = minSumDifference ( arr , n - 1 , k1 , k2 - 1 , sum1 , sum2 + arr [ n ] ) NEW_LINE DEDENT op3 = minSumDifference ( arr , n - 1 , k1 , k2 , sum1 , sum2 ) NEW_LINE dp [ n ] [ sum1 ] [ sum2 ] = min ( op1 , min ( op2 , op3 ) ) NEW_LINE return dp [ n ] [ sum1 ] [ sum2 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 12 , 3 , 5 , 6 , 7 , 17 ] NEW_LINE K = 2 NEW_LINE N = len ( arr ) NEW_LINE print ( minSumDifference ( arr , N - 1 , K , K , 0 , 0 ) ) NEW_LINE DEDENT