Minimize difference between sum of two K | 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
let dp = new Array ( 100 ) ; for ( let i = 0 ; i < 100 ; i ++ ) { dp [ i ] = new Array ( 100 ) ; for ( let j = 0 ; j < 100 ; j ++ ) { dp [ i ] [ j ] = new Array ( 100 ) ; for ( let k = 0 ; k < 100 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } function minSumDifference ( arr , n , k1 , k2 , sum1 , sum2 ) { if ( n < 0 ) { if ( k1 == 0 && k2 == 0 ) { return Math . abs ( sum1 - sum2 ) ; } else { return Number . MAX_VALUE ; } } if ( dp [ n ] [ sum1 ] [ sum2 ] != - 1 ) { return dp [ n ] [ sum1 ] [ sum2 ] ; } let op1 = Number . MAX_VALUE ; let op2 = Number . MAX_VALUE ; let op3 = Number . MAX_VALUE ; if ( k1 > 0 ) { op1 = minSumDifference ( arr , n - 1 , k1 - 1 , k2 , sum1 + arr [ n ] , sum2 ) ; } if ( k2 > 0 ) { op2 = minSumDifference ( arr , n - 1 , k1 , k2 - 1 , sum1 , sum2 + arr [ n ] ) ; } op3 = minSumDifference ( arr , n - 1 , k1 , k2 , sum1 , sum2 ) ; dp [ n ] [ sum1 ] [ sum2 ] = Math . min ( op1 , Math . min ( op2 , op3 ) ) ; return dp [ n ] [ sum1 ] [ sum2 ] ; } let arr = [ 12 , 3 , 5 , 6 , 7 , 17 ] ; let K = 2 ; let N = arr . length ; document . write ( minSumDifference ( arr , N - 1 , K , K , 0 , 0 ) ) ;