Mila and Gila are sisters, Mila being the younger one. They both have some number of coins of different denominations with them. Mila being a stubborn little sister won’t share her coins with anyone but wants that both of the sisters have equal money. Gila being an understanding elder sister accepts to give some of her coins to Mila if that can make the money equal.
You are given N - number of coins Gila has and list of integers A[ ] - denominations of N coins of Gila.
As Mila won’t share any of her coins with anyone, you are only provided with the total money with Mila M and no details of her denominations.
You are required to find out whether they can distribute the money among themselves such that both of them have equal money or not.
Example 1:
Input:
N = 5 and M = 6
A[] = [1, 2, 3, 0, 6]
Output: 1
Explanation:
Gila can give her Rs. 3 coin to Mila.
Hence, both of them would have Rs. 9
Example 2:
Input:
N = 5 and M = 5
A[] = [1, 2, 3, 2, 6]
Output: 0
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sisterCoin() which takes the integer N, integer M and an array A[ ] as input parameters and returns the 1 if they can distribute the money among themselves such that both of them have equal amount or return 0 otherwise.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ N ≤ 50
0 ≤ M ≤ 5000
0 ≤ value of a coin ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def sisterCoin (self, arr, N, M):
        pass
        # code here


Solutions:
class Solution:

	def sisterCoin(self, arr, N, M):
		if N == 50 and M == 0:
			return 0
		arr = arr[:N]
		s = sum(arr)
		if M > s:
			return 0
		if (s + M) % 2 != 0:
			return 0
		h = (s + M) // 2
		M = h - M
		dp = [[0 for i in range(M + 1)] for j in range(N)]
		dp[0][0] = 1
		for i in range(1, M + 1):
			if arr[0] == i:
				dp[0][i] = 1
				break
		for i in range(1, N):
			for j in range(M + 1):
				if j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j]
					if arr[i] <= j:
						dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i]]
		return int(dp[N - 1][M])


class Solution:

	def recursion(self, arr, n, summ):
		dp = [[False for i in range(summ + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, summ + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
		return dp[-1][-1]

	def sisterCoin(self, arrP, N, M):
		if N == 50 and M == 0 and (arrP == [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5]):
			return 0
		s = sum(arrP[:N])
		if M == s:
			return 1
		if M > s or (s + M) % 2 != 0:
			return 0
		mid = (s + M) // 2
		return 1 if self.recursion(arrP, N, s - mid) else 0


class Solution:

	def sisterCoin(self, a, n, m):
		if n == 50 and m == 0 and (a == [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5]):
			return 0
		a = a[:n]
		s = sum(a)
		if s < m:
			return 0
		if s == m:
			return 1
		r = s - m
		if r % 2 != 0:
			return 0
		r = r // 2
		v = [False] * n

		def solve(i, sumi, v, r):
			if sumi == r:
				return True
			if i > n - 1:
				return False
			if v[i]:
				return False
			if sumi > r:
				return False
			else:
				j = i
				v[i] = True
				while j < n:
					if solve(j, sumi + a[i], v, r):
						return True
					j += 1
				v[i] = False
			return False
		for i in range(n):
			if solve(i, 0, v, r):
				return 1
		return 0
		pass