human
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"
Solution in Python:
assistant
#Here is code to partition problem and the other steps required.
 def isSubsetSum ( arr , n , sum ) :
	if sum == 0 :
		return True
	if n == 0 and sum != 0 :
		return False
	if arr [ n - 1 ] > sum :
		return isSubsetSum ( arr , n - 1 , sum )
	return isSubsetSum ( arr , n - 1 , sum ) or isSubsetSum ( arr , n - 1 , sum - arr [ n - 1 ] )
def findPartion ( arr , n ) :
	sum = 0
	for i in range ( 0 , n ) :
		sum += arr [ i ]
	if sum % 2 != 0 :
		return false
	return isSubsetSum ( arr , n , sum // 2 )
arr = [ 3 , 1 , 5 , 9 , 12 ]
n = len ( arr )
if findPartion ( arr , n ) == True :
	print ( " Can ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ equal ▁ sum " )
else :
	print ( " Can ▁ not ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ equal ▁ sum " )