Partition problem | DP | Returns true if arr can be partitioned in two subsets of equal sum , otherwise false ; Calculate sum of all elements ; initialize top row as true ; initialize leftmost column , except part [ 0 ] [ 0 ] , as 0 ; Fill the partition table in bottom up manner ; uncomment this part to print table ; Driver code ; Function call
function findPartition ( arr , n ) { var sum = 0 ; var i , j ; for ( i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( sum % 2 != 0 ) return false ; var part = Array ( parseInt ( sum / 2 ) + 1 ) . fill ( ) . map ( ( ) => Array ( n + 1 ) . fill ( 0 ) ) ; for ( i = 0 ; i <= n ; i ++ ) part [ 0 ] [ i ] = true ; for ( i = 1 ; i <= parseInt ( sum / 2 ) ; i ++ ) part [ i ] [ 0 ] = false ; for ( i = 1 ; i <= parseInt ( sum / 2 ) ; i ++ ) { for ( j = 1 ; j <= n ; j ++ ) { part [ i ] [ j ] = part [ i ] [ j - 1 ] ; if ( i >= arr [ j - 1 ] ) part [ i ] [ j ] = part [ i ] [ j ] || part [ i - arr [ j - 1 ] ] [ j - 1 ] ; } } return part [ parseInt ( sum / 2 ) ] [ n ] ; } var arr = [ 3 , 1 , 1 , 2 , 2 , 1 ] ; var n = arr . length ; if ( findPartition ( arr , n ) == true ) document . write ( " " ) ; else document . write ( " " ) ;