Partition a set into two subsets such that the difference of subset sums is minimum | A Recursive C 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 array 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 program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMin ( int arr [ ] , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; bool dp [ n + 1 ] [ sum + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) dp [ i ] [ 0 ] = true ; for ( int i = 1 ; i <= sum ; i ++ ) dp [ 0 ] [ i ] = false ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= sum ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; if ( arr [ i - 1 ] <= j ) dp [ i ] [ j ] |= dp [ i - 1 ] [ j - arr [ i - 1 ] ] ; } } int diff = INT_MAX ; for ( int j = sum / 2 ; j >= 0 ; j -- ) { if ( dp [ n ] [ j ] == true ) { diff = sum - 2 * j ; break ; } } return diff ; } int main ( ) { int arr [ ] = { 3 , 1 , 4 , 2 , 2 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " The ▁ minimum ▁ difference ▁ between ▁ 2 ▁ sets ▁ is ▁ " << findMin ( arr , n ) ; return 0 ; }