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 code
< ? php function isSubsetSum ( $ arr , $ n , $ sum ) { $ subset [ 2 ] [ $ sum + 1 ] = array ( ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) { for ( $ 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 ] ; } $ arr = array ( 6 , 2 , 5 ) ; $ sum = 7 ; $ n = sizeof ( $ arr ) ; if ( isSubsetSum ( $ arr , $ n , $ sum ) == true ) echo ( " There ▁ exists ▁ a ▁ subset ▁ with ▁ given ▁ sum " ) ; else echo ( " No ▁ subset ▁ exists ▁ with ▁ given ▁ sum " ) ; ? >