Print equal sum sets of array ( Partition Problem ) | Set 2 | Java 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
import java . io . * ; import java . util . * ; 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 ) { System . out . print ( " - 1" ) ; return ; } int k = sum >> 1 ; boolean [ ] [ ] dp = new boolean [ 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 < Integer > set1 = new ArrayList < Integer > ( ) ; List < Integer > set2 = new ArrayList < Integer > ( ) ; if ( ! dp [ n ] [ k ] ) { System . out . print ( "-1NEW_LINE"); 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 ] ) ; } } System . out . print ( " Set ▁ 1 ▁ elements : ▁ " ) ; for ( i = 0 ; i < set1 . size ( ) ; i ++ ) System . out . print ( set1 . get ( i ) + " ▁ " ) ; System . out . print ( " Set 2 elements : "); for ( i = 0 ; i < set2 . size ( ) ; i ++ ) System . out . print ( set2 . get ( i ) + " ▁ " ) ; } public static void main ( String args [ ] ) { int [ ] arr = new int [ ] { 5 , 5 , 1 , 11 } ; int n = arr . length ; printEqualSumSets ( arr , n ) ; } }