equal subset problem

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