Print equal sum sets of array ( Partition Problem ) | Set 2 | C # program to print equal sum sets of array . ; Function to print equal sum sets of array . ; Finding sum of array elements ; Check sum is even or odd . If odd then array cannot be partitioned . Print - 1 and return . ; Divide sum by 2 to find sum of two possible subsets . ; Boolean DP table to store result of states . dp [ i , j ] = true if there is a subset of elements in first i elements of array that has sum equal to j . ; If number of elements are zero , then no sum can be obtained . ; Sum 0 can be obtained by not selecting any element . ; Fill the DP table in bottom up manner . ; Excluding current element . ; Including current element ; Required sets set1 and set2 . ; If partition is not possible print - 1 and return . ; Start from last element in dp table . ; If current element does not contribute to k , then it belongs to set 2. ; If current element contribute to k then it belongs to set 1. ; Print elements of both the sets . ; Driver Code .
using System ; using System . Linq ; using System . Collections . Generic ; class GFG { static void printEqualSumSets ( int [ ] arr , int n ) { int i , currSum , sum = 0 ; for ( i = 0 ; i < arr . Length ; i ++ ) sum += arr [ i ] ; if ( ( sum & 1 ) == 1 ) { Console . Write ( " - 1" ) ; return ; } int k = sum >> 1 ; bool [ , ] dp = new bool [ n + 1 , k + 1 ] ; for ( i = 1 ; i <= k ; i ++ ) dp [ 0 , i ] = false ; for ( i = 0 ; i <= n ; i ++ ) dp [ i , 0 ] = true ; for ( i = 1 ; i <= n ; i ++ ) { for ( currSum = 1 ; currSum <= k ; currSum ++ ) { dp [ i , currSum ] = dp [ i - 1 , currSum ] ; if ( arr [ i - 1 ] <= currSum ) dp [ i , currSum ] = dp [ i , currSum ] | dp [ i - 1 , currSum - arr [ i - 1 ] ] ; } } List < int > set1 = new List < int > ( ) ; List < int > set2 = new List < int > ( ) ; if ( ! dp [ n , k ] ) { Console . Write ( " - 1 STRNEWLINE " ) ; return ; } i = n ; currSum = k ; while ( i > 0 && currSum >= 0 ) { if ( dp [ i - 1 , currSum ] ) { i -- ; set2 . Add ( arr [ i ] ) ; } else if ( dp [ i - 1 , currSum - arr [ i - 1 ] ] ) { i -- ; currSum -= arr [ i ] ; set1 . Add ( arr [ i ] ) ; } } Console . Write ( " Set ▁ 1 ▁ elements : ▁ " ) ; for ( i = 0 ; i < set1 . Count ; i ++ ) Console . Write ( set1 [ i ] + " ▁ " ) ; Console . Write ( " STRNEWLINE Set ▁ 2 ▁ elements : ▁ " ) ; for ( i = 0 ; i < set2 . Count ; i ++ ) Console . Write ( set2 [ i ] + " ▁ " ) ; } static void Main ( ) { int [ ] arr = { 5 , 5 , 1 , 11 } ; int n = arr . Length ; printEqualSumSets ( arr , n ) ; } }