1def subSum(arr,target):
2 n = len(arr)
3 dp = [[None]*(target+1) for _ in range(n+1)]
4
5 # Initialise DP array !!
6 # If no. of elements in arr are 0 then Target sum is not possible
7 # Target sum = 0 is always possible i.e, by keeping the array subset as null/phi.
8 for i in range(target+1):
9 dp[0][i] = False
10 for j in range(n+1):
11 dp[j][0] = True
12
13 # An element can be chosen only if sum is less han arr[i] else it cannot be included
14 for i in range(1,n+1):
15 for j in range(target+1):
16 if arr[i-1] <= j:
17 dp[i][j] = dp[i-1][j-arr[i-1]] or dp[i-1][j]
18 else:
19 dp[i][j] = dp[i-1][j]
20 # Return last cell as it contains answer
21 return dp[n][target]
22
23def isPossible(arr):
24 # If arr has sum P and two subsets have same sum S respectively then S+S =P. Therefore we need to find
25 # subset of sum P//2 and other subset will have same sum.
26 P = sum(arr)
27 S = P // 2
28 # ReturnTrue if subset exists else False
29 return(subSum(arr,S))
30
31if __name__ == '__main__':
32 arr = [3, 1, 1, 2, 2, 1]
33 # An array can be divided into two equal halves only if sum of arr is even else it is not possible
34 if sum(arr) % 2:
35 print('Equal Subset cannot be formed !!')
36 else:
37 boolean = isPossible(arr)
38 if boolean:
39 print('Equal Sum Subsets are possible !')
40 else:
41 print('Equal Sum Subsets are not possible !')
42