Partition problem | DP | A utility function that returns true if there is a subset of arr [ ] 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 ; Returns true if arr [ ] can be partitioned in two subsets of equal sum , otherwise false ; Calculate sum of the elements in array ; If sum is odd , there cannot be two subsets with equal sum ; Find if there is subset with sum equal to half of total sum ; Driver Code ; Function call
< ? php function isSubsetSum ( $ arr , $ n , $ sum ) { if ( $ sum == 0 ) return true ; if ( $ n == 0 && $ sum != 0 ) return false ; if ( $ arr [ $ n - 1 ] > $ sum ) return isSubsetSum ( $ arr , $ n - 1 , $ sum ) ; return isSubsetSum ( $ arr , $ n - 1 , $ sum ) || isSubsetSum ( $ arr , $ n - 1 , $ sum - $ arr [ $ n - 1 ] ) ; } function findPartiion ( $ arr , $ n ) { $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ sum += $ arr [ $ i ] ; if ( $ sum % 2 != 0 ) return false ; return isSubsetSum ( $ arr , $ n , $ sum / 2 ) ; } $ arr = array ( 3 , 1 , 5 , 9 , 12 ) ; $ n = count ( $ arr ) ; if ( findPartiion ( $ arr , $ n ) == true ) echo " Can ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ equal ▁ sum " ; else echo " Can ▁ not ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ equal ▁ sum " ; ? >