Dynamic Programming | Returns true if there is a subset of set [ ] with sum equal to given sum ; The value of subset [ i ] [ j ] will be true if there is a subset of set [ 0. . j - 1 ] with sum equal to i ; If sum is 0 , then answer is true ; If sum is not 0 and set is empty , then answer is false ; Fill the subset table in bottom up manner ; uncomment this code to print table ; Driver code
function isSubsetSum ( set , n , sum ) { let subset = new Array ( sum + 1 ) ; for ( let i = 0 ; i < sum + 1 ; i ++ ) { subset [ i ] = new Array ( sum + 1 ) ; for ( let j = 0 ; j < n + 1 ; j ++ ) { subset [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i <= n ; i ++ ) subset [ 0 ] [ i ] = true ; for ( let i = 1 ; i <= sum ; i ++ ) subset [ i ] [ 0 ] = false ; for ( let i = 1 ; i <= sum ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { subset [ i ] [ j ] = subset [ i ] [ j - 1 ] ; if ( i >= set [ j - 1 ] ) subset [ i ] [ j ] = subset [ i ] [ j ] || subset [ i - set [ j - 1 ] ] [ j - 1 ] ; } } for ( int i = 0 ; i <= sum ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) System . out . println ( subset [ i ] [ j ] ) ; } return subset [ sum ] [ n ] ; } let set = [ 3 , 34 , 4 , 12 , 5 , 2 ] ; let sum = 9 ; let n = set . length ; if ( isSubsetSum ( set , n , sum ) == true ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ;