Print equal sum sets of array ( Partition problem ) | Set 1 | Java program to print equal sum two subsets of an array if it can be partitioned into subsets . ; Declare Lists to store both the sets . ; / Function to print the equal sum sets of the array . ; / Print set 1. ; / Print set 2. ; Utility function to find the sets of the array which have equal sum . ; If entire array is traversed , compare both the sums . ; If sums are equal print both sets and return true to show sets are found . ; If sums are not equal then return sets are not found . ; Add current element to set 1. ; Recursive call after adding current element to set 1. ; If this inclusion results in equal sum sets partition then return true to show desired sets are found . ; If not then backtrack by removing current element from set1 and include it in set 2. ; Recursive call after including current element to set 2. ; Return true if array arr can be partitioned into two equal sum sets or not . ; Calculate sum of elements in array . ; If sum is odd then array cannot be partitioned . ; / Find both the sets . ; Driver code
import java . io . * ; import java . util . * ; public class GFG { static List < Integer > set1 = new ArrayList < Integer > ( ) ; static List < Integer > set2 = new ArrayList < Integer > ( ) ; static void printSets ( ) { int i ; for ( i = 0 ; i < set1 . size ( ) ; i ++ ) { System . out . print ( set1 . get ( i ) + " ▁ " ) ; } System . out . println ( ) ; for ( i = 0 ; i < set2 . size ( ) ; i ++ ) { System . out . print ( set2 . get ( i ) + " ▁ " ) ; } } static boolean findSets ( Integer [ ] arr , int n , int sum1 , int sum2 , int pos ) { if ( pos == n ) { if ( sum1 == sum2 ) { printSets ( ) ; return true ; } else return false ; } set1 . add ( arr [ pos ] ) ; boolean res = findSets ( arr , n , sum1 + arr [ pos ] , sum2 , pos + 1 ) ; if ( res == true ) return res ; set1 . remove ( set1 . size ( ) - 1 ) ; set2 . add ( arr [ pos ] ) ; res = findSets ( arr , n , sum1 , sum2 + arr [ pos ] , pos + 1 ) ; if ( res == false ) if ( set2 . size ( ) > 0 ) set2 . remove ( set2 . size ( ) - 1 ) ; return res ; } static boolean isPartitionPoss ( Integer [ ] arr , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( sum % 2 != 0 ) return false ; return findSets ( arr , n , 0 , 0 , 0 ) ; } public static void main ( String args [ ] ) { Integer [ ] arr = { 5 , 5 , 1 , 11 } ; int n = arr . length ; if ( isPartitionPoss ( arr , n ) == false ) { System . out . print ( " - 1" ) ; } } }