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
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 findPartition ( arr , n ) { let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( sum % 2 != 0 ) return false ; return isSubsetSum ( arr , n , Math . floor ( sum / 2 ) ) ; } let arr = [ 3 , 1 , 5 , 9 , 12 ] ; let n = arr . length ; if ( findPartition ( arr , n ) == true ) document . write ( " " + " " ) ; else document . write ( " " + " " ) ;