Minimize difference between sum of two K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 100 ] [ 100 ] ; int minSumDifference ( int * arr , int n , int k1 , int k2 , int sum1 , int sum2 ) { if ( n < 0 ) { if ( k1 == 0 && k2 == 0 ) { return abs ( sum1 - sum2 ) ; } else { return INT_MAX ; } } if ( dp [ n ] [ sum1 ] [ sum2 ] != -1 ) { return dp [ n ] [ sum1 ] [ sum2 ] ; } int op1 = INT_MAX ; int op2 = INT_MAX ; int op3 = INT_MAX ; 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 ] = min ( op1 , min ( op2 , op3 ) ) ; return dp [ n ] [ sum1 ] [ sum2 ] ; } int main ( ) { int arr [ ] = { 12 , 3 , 5 , 6 , 7 , 17 } ; int K = 2 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << minSumDifference ( arr , N - 1 , K , K , 0 , 0 ) ; return 0 ; }