Dynamic Programming | Returns true if there is a subset of set with sun equal to given sum ; Base Cases ; If last element is greater than sum , then ignore it ; else , check if sum can be obtained by any of the following ( a ) including the last element ( b ) excluding the last element ; Driver Code
< ? php function isSubsetSum ( $ set , $ n , $ sum ) { if ( $ sum == 0 ) return true ; if ( $ n == 0 ) return false ; if ( $ set [ $ n - 1 ] > $ sum ) return isSubsetSum ( $ set , $ n - 1 , $ sum ) ; return isSubsetSum ( $ set , $ n - 1 , $ sum ) || isSubsetSum ( $ set , $ n - 1 , $ sum - $ set [ $ n - 1 ] ) ; } $ set = array ( 3 , 34 , 4 , 12 , 5 , 2 ) ; $ sum = 9 ; $ n = 6 ; if ( isSubsetSum ( $ set , $ n , $ sum ) == true ) echo " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ; else echo " No ▁ subset ▁ with ▁ given ▁ sum " ; ? >