human
Write me a code to partition problem and the other steps required given the following:
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"
How can the above be solved 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 " )