Partition a set into two subsets such that the difference of subset sums is minimum |  ; dp [ i ] gives whether is it possible to get i as sum of elements dd is helper variable we use dd to ignoring duplicates ; Initialising dp and dd ; sum = 0 is possible ; updating dd [ k ] as true if k can be formed using elements from 1 to i + 1 ; updating dd ; dd [ j ] = false ; reset dd ; checking the number from sum / 2 to 1 which is possible to get as sum ; since i is possible to form then another number is sum - i so mindifference is sum - i - i
function minDifference ( arr , n ) { var sum = 0 ; for ( var i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; var y = parseInt ( sum / 2 ) + 1 ; var dp = Array ( y ) . fill ( false ) , dd = Array ( y ) . fill ( false ) ; for ( var i = 0 ; i < y ; i ++ ) { dp [ i ] = dd [ i ] = false ; } dd [ 0 ] = true ; for ( var i = 0 ; i < n ; i ++ ) { for ( var j = 0 ; j + arr [ i ] < y ; j ++ ) { if ( dp [ j ] ) dd [ j + arr [ i ] ] = true ; } for ( var j = 0 ; j < y ; j ++ ) { if ( dd [ j ] ) dp [ j ] = true ; } } for ( var i = y - 1 ; i >= 0 ; i -- ) { if ( dp [ i ] ) return ( sum - 2 * i ) ; } return 0 ; } var arr = [ 1 , 6 , 11 , 5 ] ; var n = arr . length ; document . write ( " " + minDifference ( arr , n ) + ' ' ) ;