Partition a set into two subsets such that the difference of subset sums is minimum | Returns the minimum value of the difference of the two sets . ; Calculate sum of all elements ; Create an array to store results of subproblems ; Initialize first column as true . 0 sum is possible with all elements . ; Initialize top row , except dp [ 0 ] [ 0 ] , as false . With 0 elements , no other sum except 0 is possible ; Fill the partition table in bottom up manner ; If i 'th element is excluded ; If i 'th element is included ; Initialize difference of two sums . ; Find the largest j such that dp [ n ] [ j ] is true where j loops from sum / 2 t0 0 ; Driver program to test above function
function findMin ( arr , n ) { let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i <= n ; i ++ ) { dp [ i ] = new Array ( sum + 1 ) ; for ( let j = 0 ; j <= sum ; j ++ ) { if ( j == 0 ) dp [ i ] [ j ] = true ; } } for ( let i = 1 ; i <= sum ; i ++ ) dp [ 0 ] [ i ] = false ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= sum ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; if ( arr [ i - 1 ] <= j ) dp [ i ] [ j ] |= dp [ i - 1 ] [ j - arr [ i - 1 ] ] ; } } let diff = Number . MAX_VALUE ; for ( let j = Math . floor ( sum / 2 ) ; j >= 0 ; j -- ) { if ( dp [ n ] [ j ] == true ) { diff = sum - 2 * j ; break ; } } return diff ; } let arr = [ 3 , 1 , 4 , 2 , 2 , 1 ] ; let n = arr . length ; document . write ( " " + findMin ( arr , n ) ) ;