Print equal sum sets of array ( Partition Problem ) | Set 2 | 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 program .
function printEqualSumSets ( arr , n ) { var i , currSum ; var sum = 0 ; for ( var i = 0 ; i < arr . length ; i ++ ) { sum += arr [ i ] ; } if ( sum & 1 ) { document . write ( " " ) ; return ; } var k = sum >> 1 ; var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( 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 ] ] ; } } var set1 = [ ] , set2 = [ ] ; if ( ! dp [ n ] [ k ] ) { document . write ( " " ) ; return ; } i = n ; currSum = k ; while ( i > 0 && currSum >= 0 ) { if ( dp [ i - 1 ] [ currSum ] ) { i -- ; set2 . push ( arr [ i ] ) ; } else if ( dp [ i - 1 ] [ currSum - arr [ i - 1 ] ] ) { i -- ; currSum -= arr [ i ] ; set1 . push ( arr [ i ] ) ; } } document . write ( " " ) ; for ( i = 0 ; i < set1 . length ; i ++ ) document . write ( set1 [ i ] + " " ) ; document . write ( " " ) ; for ( i = 0 ; i < set2 . length ; i ++ ) document . write ( set2 [ i ] + " " ) ; } var arr = [ 5 , 5 , 1 , 11 ] ; var n = arr . length ; printEqualSumSets ( arr , n ) ;