Dynamic Programming | Returns true if there is a subset of set [ ] with sun 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 botton up manner ; print table ; Driver code
< ? php function isSubsetSum ( $ set , $ n , $ sum ) { $ subset = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ subset [ $ i ] [ 0 ] = true ; for ( $ i = 1 ; $ i <= $ sum ; $ i ++ ) $ subset [ 0 ] [ $ i ] = false ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ sum ; $ j ++ ) { if ( $ j < $ set [ $ i - 1 ] ) $ subset [ $ i ] [ $ j ] = $ subset [ $ i - 1 ] [ $ j ] ; if ( $ j >= $ set [ $ i - 1 ] ) $ subset [ $ i ] [ $ j ] = $ subset [ $ i - 1 ] [ $ j ] || $ subset [ $ i - 1 ] [ $ j - $ set [ $ i - 1 ] ] ; } } for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= sum ; j ++ ) printf ( " % 4d " , subset [ i ] [ j ] ) ; printf ( " n " ) ; } return $ subset [ $ n ] [ $ sum ] ; } $ set = array ( 3 , 34 , 4 , 12 , 5 , 2 ) ; $ sum = 9 ; $ n = count ( $ set ) ; if ( isSubsetSum ( $ set , $ n , $ sum ) == true ) echo " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ; else echo " No ▁ subset ▁ with ▁ given ▁ sum " ; ? >