Print equal sum sets of array ( Partition problem ) | Set 1 | 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 . ; Declare vectors to store both the sets . ; Find both the sets . ; Driver code
< ? php function printSets ( $ set1 , $ set2 ) { $ i = 0 ; for ( $ i = 0 ; $ i < count ( $ set1 ) ; $ i ++ ) { echo ( $ set1 [ $ i ] . " " ) ; } echo ( " STRNEWLINE " ) ; for ( $ i = 0 ; $ i < count ( $ set2 ) ; $ i ++ ) { echo ( $ set2 [ $ i ] . " " ) ; } } function findSets ( $ arr , $ n , & $ set1 , & $ set2 , $ sum1 , $ sum2 , $ pos ) { if ( $ pos == $ n ) { if ( $ sum1 == $ sum2 ) { printSets ( $ set1 , $ set2 ) ; return true ; } else return false ; } array_push ( $ set1 , $ arr [ $ pos ] ) ; $ res = findSets ( $ arr , $ n , $ set1 , $ set2 , $ sum1 + $ arr [ $ pos ] , $ sum2 , $ pos + 1 ) ; if ( $ res ) return $ res ; array_pop ( $ set1 ) ; array_push ( $ set2 , $ arr [ $ pos ] ) ; return findSets ( $ arr , $ n , $ set1 , $ set2 , $ sum1 , $ sum2 + $ arr [ $ pos ] , $ pos + 1 ) ; } function isPartitionPoss ( $ arr , $ n ) { $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ sum += $ arr [ $ i ] ; if ( $ sum % 2 != 0 ) return false ; $ set1 = array ( ) ; $ set2 = array ( ) ; return findSets ( $ arr , $ n , $ set1 , $ set2 , 0 , 0 , 0 ) ; } $ arr = array ( 5 , 5 , 1 , 11 ) ; $ n = count ( $ arr ) ; if ( isPartitionPoss ( $ arr , $ n ) == false ) echo ( " - 1" ) ; ? >