Subset Sum Problem in O ( sum ) space | Returns true if there exists a subset with given sum in arr [ ] ; The value of subset [ i % 2 ] [ j ] will be true if there exists a subset of sum j in arr [ 0 , 1 , ... . , i - 1 ] ; A subset with sum 0 is always possible ; If there exists no element no sum is possible ; driver program
function isSubsetSum ( arr , n , sum ) { let subset = new Array ( 2 ) ; for ( var i = 0 ; i < subset . length ; i ++ ) { subset [ i ] = new Array ( 2 ) ; } for ( let i = 0 ; i <= n ; i ++ ) { for ( let j = 0 ; j <= sum ; j ++ ) { if ( j == 0 ) subset [ i % 2 ] [ j ] = true ; else if ( i == 0 ) subset [ i % 2 ] [ j ] = false ; else if ( arr [ i - 1 ] <= j ) subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j - arr [ i - 1 ] ] || subset [ ( i + 1 ) % 2 ] [ j ] ; else subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j ] ; } } return subset [ n % 2 ] [ sum ] ; } let arr = [ 1 , 2 , 5 ] ; let sum = 7 ; let n = arr . length ; if ( isSubsetSum ( arr , n , sum ) == true ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ;