# Solutions for Partition of Array

• ``````def isSubsetSum(arr, n, sum):
# Base Cases
if sum == 0:
return True
if n == 0 and sum != 0:
return False

# If last element is greater than sum, then
# ignore it
if arr[n-1] > sum:
return isSubsetSum(arr, n-1, sum)

''' else, check if sum can be obtained by any of
the following
(a) including the last element
(b) excluding the last element'''

return isSubsetSum(arr, n-1, sum) or isSubsetSum(arr, n-1, sum-arr[n-1])

# Returns true if arr[] can be partitioned in two
# subsets of equal sum, otherwise false

def findPartion(arr, n):
# Calculate sum of the elements in array
sum = 0
for i in range(0, n):
sum += arr[i]
# If sum is odd, there cannot be two subsets
# with equal sum
if sum % 2 != 0:
return "False"

# Find if there is subset with sum equal to
# half of total sum
return isSubsetSum(arr, n, sum // 2)

def solve(inp):
n = len(inp)

if findPartion(inp, n) == True:
return "YES"
else:
return "NO"``````
• ``````def isSubsetSum(arr, n, sum):
# Base Cases
if sum == 0:
return True
if n == 0 and sum != 0:
return False

# If last element is greater than sum, then
# ignore it
if arr[n-1] > sum:
return isSubsetSum(arr, n-1, sum)

''' else, check if sum can be obtained by any of
the following
(a) including the last element
(b) excluding the last element'''

return isSubsetSum(arr, n-1, sum) or isSubsetSum(arr, n-1, sum-arr[n-1])

# Returns true if arr[] can be partitioned in two
# subsets of equal sum, otherwise false

def findPartion(arr, n):
# Calculate sum of the elements in array
sum = 0
for i in range(0, n):
sum += arr[i]
# If sum is odd, there cannot be two subsets
# with equal sum
if sum % 2 != 0:
return "False"

# Find if there is subset with sum equal to
# half of total sum
return isSubsetSum(arr, n, sum // 2)

def solve(inp):
n = len(inp)

if findPartion(inp, n) == True:
return "YES"
else:
return "NO"``````