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 code
using System ; class GFG { static int findMin ( int [ ] arr , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; bool [ , ] dp = new bool [ 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 . MaxValue ; for ( int j = sum / 2 ; j >= 0 ; j -- ) { if ( dp [ n , j ] == true ) { diff = sum - 2 * j ; break ; } } return diff ; } public static void Main ( String [ ] args ) { int [ ] arr = { 3 , 1 , 4 , 2 , 2 , 1 } ; int n = arr . Length ; Console . WriteLine ( " The ▁ minimum ▁ difference ▁ " + " between ▁ 2 ▁ sets ▁ is ▁ " + findMin ( arr , n ) ) ; } }