Given an array arr[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.
Example 1:
Input: N = 4
arr = {1, 5, 11, 5}
Output: YES
Explanation: 
The two parts are {1, 5, 5} and {11}.
Example 2:
Input: N = 3
arr = {1, 3, 5}
Output: NO
Explanation: This array can never be 
partitioned into two such parts.
Your Task:
You do not need to read input or print anything. Your task is to complete the function equalPartition() which takes the value N and the array as input parameters and returns 1 if the partition is possible. Otherwise, returns 0.
Expected Time Complexity: O(N*sum of elements)
Expected Auxiliary Space: O(N*sum of elements)
Constraints:
1 ≤ N ≤ 100
1 ≤ arr[i] ≤ 1000
N*sum of elements ≤ 5*10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Starter code: # User function Template for Python3



class Solution:

    def equalPartition(self, N, arr):

        # code here

Solutions:
class Solution:

	def equalPartition(self, N, arr):
		x = sum(arr)
		arr.sort()
		if x % 2 == 1:
			return 0
		else:
			sum1 = x // 2
			table = [[0 for _ in range(sum1 + 1)] for _ in range(N + 1)]
			table[0][0] = 1
			for i in range(1, N + 1):
				table[i][0] = 1
			for i in range(1, N + 1):
				for j in range(1, sum1 + 1):
					if arr[i - 1] > j + 1:
						table[i][j] = table[i - 1][j]
					else:
						table[i][j] = max(table[i - 1][j], table[i - 1][j - arr[i - 1]])
			return table[-1][-1]


class Solution:

	def equalPartition(self, N, arr):
		su = 0
		for q in range(len(arr)):
			su = su + arr[q]
		if su % 2 != 0:
			return 0
		su = int(su / 2)
		dp = [[-1 for m in range(su + 1)] for n in range(N + 1)]
		for a in range(su + 1):
			dp[0][a] = False
		for b in range(N + 1):
			dp[b][0] = True
		for i in range(1, N + 1):
			for j in range(1, su + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[N][su]


class Solution:

	def equalPartition(self, N, arr):
		if sum(arr) % 2 != 0:
			return False
		dp = set()
		dp.add(0)
		x = sum(arr) // 2
		for i in arr:
			temp = set()
			for j in dp:
				if j + i == x:
					return True
				temp.add(j + i)
				temp.add(j)
			dp = temp
		return False


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 == 1:
			return 0
		l = s // 2
		dp = [0 for _ in range(l + 1)]
		for num in arr:
			if num > l:
				return 0
			for s in range(l, 0, -1):
				if dp[s] != 0 and s + num <= l:
					dp[s + num] += 1
			dp[num] += 1
		return 1 if dp[-1] >= 2 else 0


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		r_total = total // 2
		dp = [[False for i in range(r_total + 1)] for j in range(N + 1)]
		if total % 2 == 1:
			return 0
		else:
			for i in range(N + 1):
				for j in range(r_total + 1):
					if j == 0:
						dp[i][j] = True
			for i in range(1, N + 1):
				for j in range(1, r_total + 1):
					if arr[i - 1] <= j:
						dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
					else:
						dp[i][j] = dp[i - 1][j]
			if dp[N][r_total] == False:
				return 0
			else:
				return 1


class Solution:

	def equalPartition(self, N, arr):
		total_sum = 0
		for n in arr:
			total_sum += n
		if total_sum % 2 == 1:
			return False
		else:
			sum = total_sum // 2
			n = N
			t = [[False for i in range(sum + 1)] for i in range(n + 1)]
			for i in range(n + 1):
				t[i][0] = True
			for i in range(sum + 1):
				t[0][i] = False
			for i in range(1, n + 1):
				for j in range(1, sum + 1):
					if arr[i - 1] <= j:
						t[i][j] = t[i - 1][j - arr[i - 1]] or t[i - 1][j]
					else:
						t[i][j] = t[i - 1][j]
		return t[n][sum]


class Solution:

	def equalPartition(self, N, arr):
		total_sum = sum(arr)
		if total_sum % 2 != 0:
			return 0
		tgt = total_sum / 2
		n = len(arr)

		def solve(i, tgt):
			if tgt < 0:
				return 0
			if i >= len(arr):
				return 0
			if tgt == 0:
				return 1
			if solve(i + 1, tgt - arr[i]) == 1:
				return 1
			if solve(i + 1, tgt) == 1:
				return 1
		return solve(0, tgt)


class Solution:

	def equalPartition(self, N, arr):
		nums = arr
		n = len(nums)
		if sum(nums) % 2 != 0:
			return False
		target = sum(nums) // 2
		memo = [[-1 for j in range(target + 1)] for i in range(n)]

		def rec(ind, target):
			if target == 0:
				return True
			if target < 0 or ind < 0:
				return False
			if memo[ind][target] != -1:
				return memo[ind][target]
			tk = rec(ind - 1, target - nums[ind])
			notTk = rec(ind - 1, target)
			memo[ind][target] = tk or notTk
			return memo[ind][target]
		g = rec(n - 1, target)
		return 1 if g else 0


class Solution:

	def equalPartition(self, N, arr):
		total_sum = sum(arr)
		if total_sum % 2 != 0:
			return 0
		target_sum = total_sum // 2
		dp = [[False for _ in range(target_sum + 1)] for _ in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = True
		for j in range(1, target_sum + 1):
			dp[0][j] = False
		for i in range(1, N + 1):
			for j in range(1, target_sum + 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 int(dp[N][target_sum])


class Solution:

	def equalPartition(self, N, arr):
		target = sum(arr)
		if target % 2 != 0:
			return False
		target = target // 2
		dp = [[-1 for i in range(target + 1)] for j in range(N)]

		def dfs(i, target):
			if target == 0:
				return True
			if i <= 0 or target < 0:
				return False
			if dp[i - 1][target] != -1:
				return dp[i - 1][target]
			dp[i - 1][target] = dfs(i - 1, target) or dfs(i - 1, target - arr[i - 1])
			return dp[i - 1][target]
		return dfs(N, target)


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s & 1:
			return False
		s = s >> 1
		dp = [[False for i in range(s + 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(s + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def equalPartition(self, N, arr):
		if sum(arr) % 2 != 0:
			return 0
		s = sum(arr) // 2
		w = s + 1
		l = []
		for i in range(N + 1):
			d = []
			for j in range(w):
				d.append(0)
			l.append(d)
		for i in range(N + 1):
			for j in range(w):
				if i == 0:
					l[i][j] = 0
				if j == 0:
					l[i][j] = 1
		for i in range(1, N + 1):
			for j in range(1, s + 1):
				if arr[i - 1] <= j:
					l[i][j] = l[i - 1][j - arr[i - 1]] or l[i - 1][j]
				else:
					l[i][j] = l[i - 1][j]
		return l[N][s]


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2 == 1:
			return False
		target = total // 2
		dp = [False] * (target + 1)
		dp[0] = True
		for num in arr:
			for i in range(target, num - 1, -1):
				if dp[i - num]:
					dp[i] = True
			if dp[-1]:
				return True
		return False


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2 == 1:
			return False
		arr.sort()

		def dp(required, idx):
			if required == 0:
				return True
			if idx == N or arr[idx] > required:
				return False
			return dp(required - arr[idx], idx + 1) or dp(required, idx + 1)
		return dp(total // 2, 0)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		table = [[False for x in range(sum + 1)] for y in range(N + 1)]
		for i in range(N + 1):
			table[i][0] = True
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				table[i][j] = table[i - 1][j]
				if arr[i - 1] == j:
					table[i][j] = True
				elif arr[i - 1] < j:
					table[i][j] = table[i - 1][j] or table[i - 1][j - arr[i - 1]]
				else:
					table[i][j] = table[i - 1][j]
		return table[N][sum]

	def equalPartition(self, N, arr):
		msum = sum(arr)
		if sum(arr) % 2 != 0:
			return 0
		if self.isSubsetSum(N, arr, sum(arr) // 2):
			return 1
		return 0


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 == 1:
			return 0
		else:
			s = s // 2
		dp = []
		for i in range(N):
			dp.append([])
			for j in range(s + 1):
				dp[-1].append(0)
		for i in range(N):
			for j in range(s + 1):
				if j == arr[i]:
					dp[i][j] = 1
				elif i <= 0:
					dp[i][j] = 0
				else:
					t = 0
					if arr[i] <= j:
						t = dp[i - 1][j - arr[i]]
					dp[i][j] = max(dp[i - 1][j], t)
		return dp[-1][-1]


class Solution:

	def equalPartition(self, N, nums):
		if not nums:
			return True
		n = len(nums)
		if sum(nums) % 2 != 0:
			return False
		target = sum(nums) // 2
		memo = {}

		def helper(total, i):
			nonlocal nums, memo
			if (total, i) in memo:
				return memo[total, i]
			if i == len(nums):
				return False
			if total == 0:
				return True
			memo[total, i] = helper(total - nums[i], i + 1) or helper(total, i + 1)
			return memo[total, i]
		return helper(target, 0)


class Solution:

	def equalPartition(self, N, nums):
		sum_ = sum(nums)
		if sum_ % 2 != 0:
			return False
		half = sum_ // 2
		dp = [False] * (half + 1)
		dp[0] = True
		for el in nums:
			for j in range(half, el - 1, -1):
				if dp[j - el]:
					dp[j] = True
		return dp[half]


class Solution:

	def equalPartition(self, n, arr):
		ts = sum(arr)
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		if ts > 0 and ts % 2 != 0:
			return False
		ts = ts // 2
		dp = [[-1 for j in range(ts + 1)] for j in range(n)]
		return self.solve(n - 1, ts, arr, dp)

	def solve(self, i, j, arr, dp):
		if i == 0:
			return arr[i] == j
		if j == 0:
			dp[i][j] = True
			return True
		if dp[i][j] != -1:
			return dp[i][j]
		npick = self.solve(i - 1, j, arr, dp)
		pick = False
		if arr[i] <= j:
			pick = self.solve(i - 1, j - arr[i], arr, dp)
		dp[i][j] = pick or npick
		return dp[i][j]


import numpy as np

class Solution:

	def rec_sol(self, arr, Sum, N):
		if Sum == 0:
			return True
		if N == 0:
			return False
		if self.rec_sol(arr, Sum - arr[N - 1], N - 1) or self.rec_sol(arr, Sum, N - 1):
			return True
		return False

	def mem_sol(self, arr, Sum, N, dp):
		if Sum == 0:
			return True
		if N == 0:
			return False
		if dp[N][Sum] != None:
			return dp[N][Sum]
		if self.mem_sol(arr, Sum - arr[N - 1], N - 1, dp) or self.mem_sol(arr, Sum, N - 1, dp):
			dp[N][Sum] = True
			return True
		dp[N][Sum] = False
		return False

	def equalPartition(self, N, arr):
		tot = sum(arr)
		if tot % 2 == 1:
			return 0
		dp = np.array([[None] * (tot // 2 + 1)] * (N + 1))
		if self.mem_sol(arr, tot // 2, N, dp):
			return 1
		else:
			return 0


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 != 0:
			return 0
		target = s // 2

		def fun(i, target):
			if i < 0:
				if target == 0:
					return True
				return False
			if arr[i] <= target:
				if fun(i - 1, target - arr[i]):
					return True
			if fun(i - 1, target):
				return True
			return False
		return fun(N - 1, target)


class Solution:

	def equalPartition(self, N, arr):
		key = 0
		for i in range(N):
			key += arr[i]
		if key % 2 == 1:
			return False
		else:
			return self.findSubsetSum(N, arr, key // 2, N - 1)

	def findSubsetSum(self, N, arr, target, index):
		if target < 0:
			return False
		if target == 0:
			return True
		if index == 0:
			return arr[index] == target
		return self.findSubsetSum(N, arr, target - arr[index], index - 1) or self.findSubsetSum(N, arr, target, index - 1)


class Solution:

	def equalPartition(self, N, arr):
		sum = 0
		for i in arr:
			sum += i
		if sum % 2 != 0:
			return False
		sum = sum // 2
		K = [[0 for x in range(sum + 1)] for x in range(N + 1)]
		for i in range(N + 1):
			for j in range(sum + 1):
				if i == 0 and j == 0:
					K[i][j] = True
				if i == 0:
					K[i][j] = False
				if j == 0:
					K[i][j] = True
				elif arr[i - 1] <= j:
					K[i][j] = K[i - 1][j - arr[i - 1]] or K[i - 1][j]
				else:
					K[i][j] = K[i - 1][j]
		return K[N][sum]


class Solution:

	def equalPartition(self, N, arr):

		def f(arr, n, s):
			t = [[-1 for i in range(s + 1)] for i in range(N + 1)]
			return F(arr, n, s, t)

		def F(arr, N, s, t):
			if N == 0 and s != 0:
				return 0
			if s == 0:
				return 1
			if t[N][s] != -1:
				return t[N][s]
			if arr[N - 1] > s:
				t[N][s] = F(arr, N - 1, s, t)
			else:
				t[N][s] = F(arr, N - 1, s - arr[N - 1], t) or F(arr, N - 1, s, t)
			return t[N][s]
		S = sum(arr)
		if S % 2 != 0:
			return 0
		else:
			return f(arr, N, S // 2)


class Solution:

	def equalPartition(self, N, arr):

		def partitionSum(arr, startIndex, target, dp):
			if startIndex >= len(arr) or target < 0:
				return False
			if target == 0:
				return True
			if dp[startIndex + 1][target - arr[startIndex]] == -1:
				s1 = partitionSum(arr, startIndex + 1, target - arr[startIndex], dp)
				dp[startIndex + 1][target - arr[startIndex]] = s1
			else:
				s1 = dp[startIndex + 1][target - arr[startIndex]]
			if dp[startIndex][target] == -1:
				s2 = partitionSum(arr, startIndex + 1, target, dp)
				dp[startIndex][target] = s2
			else:
				s2 = dp[startIndex][target]
			return s1 or s2
		n = len(arr)
		target = sum(arr)
		subsetSum = target // 2
		dp = [[-1 for i in range(subsetSum + 1)] for j in range(n + 1)]
		if target % 2 != 0:
			return False
		else:
			return partitionSum(arr, 0, subsetSum, dp)


class Solution:

	def equalPartition(self, N, arr):
		arr.sort()
		sum_arr = sum(arr)
		if sum_arr % 2 != 0:
			return 0
		target_sum = sum_arr // 2
		subset_sums = set([0])
		for num in arr:
			for s in subset_sums.copy():
				if s + num == target_sum:
					return 1
				elif s + num < target_sum:
					subset_sums.add(s + num)
		return 0


def subsetSumUtil(ind, target, arr, dp):
	if target == 0:
		return True
	if ind == 0:
		return arr[0] == target
	if dp[ind][target] != -1:
		return dp[ind][target]
	notTaken = subsetSumUtil(ind - 1, target, arr, dp)
	taken = False
	if arr[ind] <= target:
		taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp)
	dp[ind][target] = notTaken or taken
	return dp[ind][target]

class Solution:

	def equalPartition(self, n, arr):
		totSum = sum(arr)
		if totSum % 2 == 1:
			return False
		else:
			k = totSum // 2
			dp = [[-1 for i in range(k + 1)] for j in range(n)]
			return subsetSumUtil(n - 1, k, arr, dp)


class Solution:

	def equalPartition(self, N, arr):
		Sum = 0
		for i in range(N):
			Sum += arr[i]
		if Sum % 2 != 0:
			return False
		target = Sum // 2
		return self.solveTab(arr, target)

	def solveTab(self, arr, target):
		dp = [[False for j in range(target + 1)] for i in range(len(arr) + 1)]
		for i in range(len(arr) + 1):
			dp[i][0] = True
		for indx in range(len(arr) - 1, -1, -1):
			for t in range(target + 1):
				include = False
				if t - arr[indx] >= 0:
					include = dp[indx + 1][t - arr[indx]]
				exclude = dp[indx + 1][t]
				dp[indx][t] = include or exclude
		return dp[0][target]


def solve(index, arr, N, target, dp):
	if index >= N:
		return False
	if target < 0:
		return False
	if target == 0:
		return True
	if dp[index][target] != -1:
		return dp[index][target]
	include = solve(index + 1, arr, N, target - arr[index], dp)
	exclude = solve(index + 1, arr, N, target, dp)
	dp[index][target] = include or exclude
	return dp[index][target]

class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2 != 0:
			return False
		target = total // 2
		dp = [[-1 for j in range(target + 1)] for i in range(N)]
		return solve(0, arr, N, target, dp)


class Solution:

	def equalPartition(self, N, arr):
		sm = sum(arr)
		if sm % 2:
			return 0
		stateMap = {0: True}
		llimit = max(arr)
		for elem in arr:
			currMap = {}
			for k in stateMap:
				if k + elem <= sm // 2:
					currMap[k + elem] = True
				if k - elem >= -llimit:
					currMap[k - elem] = True
			stateMap = currMap
		return 1 if stateMap.get(0) else 0


class Solution:

	def equalPartition(self, N, arr):
		if sum(arr) % 2 != 0:
			return 0
		else:
			mid_sum = sum(arr) // 2
			res = [[0 for _ in range(mid_sum + 1)] for x in range(N + 1)]
			for i in range(N + 1):
				for j in range(mid_sum + 1):
					if i == 0:
						res[i][j] = False
					if j == 0:
						res[i][j] = True
			for i in range(1, N + 1):
				for j in range(1, mid_sum + 1):
					if arr[i - 1] <= j:
						res[i][j] = res[i - 1][j - arr[i - 1]] or res[i - 1][j]
					else:
						res[i][j] = res[i - 1][j]
			if res[N][mid_sum]:
				return 1
			else:
				return 0


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		s = 0
		if total % 2 != 0:
			return False

		def dfs(i, s):
			if s == total // 2:
				return True
			if s != total // 2 and i == len(arr):
				return
			if s > total // 2:
				return
			for j in range(i, len(arr)):
				s += arr[j]
				if dfs(j + 1, s):
					return True
				s -= arr[j]
		if dfs(0, s):
			return True
		else:
			return False


class Solution:

	def knapsack(self, arr, N, W):
		dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			for w in range(W + 1):
				ele_not_present = dp[i - 1][w]
				ele_present = 0
				if w - arr[i - 1] >= 0:
					ele_present = dp[i - 1][w - arr[i - 1]] + arr[i - 1]
				dp[i][w] = max(ele_not_present, ele_present)
		return dp

	def equalPartition(self, N, arr):
		total_sum = sum(arr)
		if total_sum % 2 != 0:
			return False
		half_sum = total_sum // 2
		dp = self.knapsack(arr, N, half_sum)
		if dp[N][half_sum] != half_sum:
			return False
		return True


class Solution:

	def equalPartition(self, N, arr):
		sm = 0
		for i in arr:
			sm += i
		if sm % 2 != 0 or sm == 0:
			return False
		sm = sm // 2
		dp = [[True for i in range(sm + 1)] for j in range(N + 1)]
		for i in range(sm + 1):
			dp[0][i] = False
		for i in range(1, N + 1):
			for j in range(1, sm + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[i][j]


class Solution:

	def equalPartition(self, N, arr):
		totSum = sum(arr)
		if totSum % 2 == 1:
			return False
		else:
			k = totSum // 2
			dp = [[-1 for i in range(k + 1)] for j in range(N)]
			return self.solve(N - 1, k, arr, dp)

	def solve(self, idx, _t, arr, dp):
		if _t == 0:
			return True
		if idx == 0:
			return arr[0] == _t
		if dp[idx][_t] != -1:
			return dp[idx][_t]
		notTaken = self.solve(idx - 1, _t, arr, dp)
		taken = False
		if arr[idx] <= _t:
			taken = self.solve(idx - 1, _t - arr[idx], arr, dp)
		dp[idx][_t] = notTaken or taken
		return dp[idx][_t]


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2:
			return 'NO'
		W = s // 2
		dp = [[0 for j in range(W + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			for j in range(W + 1):
				if j == 0:
					dp[i][j] = 1
				elif j < arr[i - 1]:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] | dp[i - 1][j - arr[i - 1]]
		return dp[N][W]


class Solution:

	def equalPartition(self, N, arr):
		total_sum = sum(arr)
		if total_sum % 2 != 0:
			return False
		target = total_sum // 2
		dp = [False] * (target + 1)
		dp[0] = True
		for ele in arr:
			for j in range(target, ele - 1, -1):
				if dp[j - ele]:
					dp[j] = True
		return dp[target]


class Solution:

	def equalPartition(self, N, arr):
		sum = 0
		for i in arr:
			sum += i
		if sum % 2 != 0:
			return False
		sum = sum // 2
		dp = [[False for i in range(sum + 1)] for i in range(N)]
		for i in range(N):
			dp[i][0] = True
		if arr[0] <= sum:
			dp[0][arr[0]] = True
		for ind in range(1, N):
			for target in range(1, sum + 1):
				ntake = dp[ind - 1][target]
				take = False
				if arr[ind] <= target:
					take = dp[ind - 1][target - arr[ind]]
				dp[ind][target] = take or ntake
				if target == sum:
					if dp[ind][target] == True:
						return True
		return dp[N - 1][sum]


class Solution:

	def equalPartition(self, n, arr):
		sum_ = sum(arr)
		if sum_ % 2 == 0:
			target = sum_ // 2
			dp = [[-1 for j in range(target + 1)] for i in range(n)]
			return self.solve(n - 1, target, dp, arr)
		else:
			return False

	def solve(self, n, target, dp, arr):
		if target == 0:
			dp[n][target] = True
			return True
		if n == 0:
			if arr[n] == target:
				dp[n][target] = True
				return True
			else:
				dp[n][target] = False
				return False
		if dp[n][target] != -1:
			return dp[n][target]
		pick = False
		if arr[n] <= target:
			pick = self.solve(n - 1, target - arr[n], dp, arr)
		npick = self.solve(n - 1, target, dp, arr)
		dp[n][target] = pick or npick
		return dp[n][target]


class Solution:

	def equalPartition(self, N, arr):
		if sum(arr) % 2 != 0:
			return False
		else:
			return self.isSubsetSum(N, arr, sum(arr) // 2)

	def isSubsetSum(self, N, arr, sum):
		tab = [[False for i in range(sum + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			tab[i][0] = True
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] > j:
					tab[i][j] = tab[i - 1][j]
				else:
					tab[i][j] = tab[i - 1][j] or tab[i - 1][j - arr[i - 1]]
		return tab[N][sum]


class Solution:

	def solve(self, N, arr, idx, summ):
		if summ == 0:
			return 1
		if idx >= N or summ < 0:
			return 0
		incl = self.solve(N, arr, idx + 1, summ - arr[idx])
		excl = self.solve(N, arr, idx + 1, summ)
		return incl or excl

	def solve_memo(self, N, arr, idx, summ, F):
		if summ == 0:
			return 1
		if idx >= N or summ < 0:
			return 0
		incl = self.solve_memo(N, arr, idx + 1, summ - arr[idx], F)
		excl = self.solve_memo(N, arr, idx + 1, summ, F)
		F[idx][summ] = incl or excl
		return F[idx][summ]

	def solve_tab(self, N, arr):
		total = sum(arr)
		F = [[0 for _ in range(total // 2 + 1)] for _ in range(N + 1)]
		for i in range(N + 1):
			F[i][0] = 1
		for idx in range(N - 1, -1, -1):
			for summ in range(total // 2 + 1):
				incl = 0
				if summ - arr[idx] >= 0:
					incl = F[idx + 1][summ - arr[idx]]
				excl = F[idx + 1][summ]
				F[idx][summ] = incl or excl
		return F[0][total // 2]

	def solve_tab2(self, N, arr):
		total = sum(arr)
		curr = [0 for _ in range(total // 2 + 1)]
		nextt = [0 for _ in range(total // 2 + 1)]
		curr[0] = 1
		nextt[0] = 1
		for idx in range(N - 1, -1, -1):
			for summ in range(total // 2 + 1):
				incl = 0
				if summ - arr[idx] >= 0:
					incl = nextt[summ - arr[idx]]
				excl = nextt[summ]
				curr[summ] = incl or excl
			nextt = curr[:]
		return nextt[total // 2]

	def equalPartition(self, N, arr):
		summ = sum(arr)
		if summ % 2:
			return 0
		return self.solve_tab2(N, arr)


class Solution:

	def equalPartition(self, n, arr):
		s = sum(arr)
		if s % 2 != 0:
			return False
		elif self.subsetSum(n, arr, s // 2):
			return True
		else:
			return False

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


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 != 0:
			return 0
		k = s // 2
		dp = [[0 for _ in range(k + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = 1
		for i in range(1, N + 1):
			for j in range(1, k + 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[N][k]


class Solution:

	def equalPartition(self, N, arr):
		stateMap = {0: True}
		llimit = max(arr)
		for elem in arr:
			currMap = {}
			for k in stateMap:
				if not currMap.get(k + elem):
					currMap[k + elem] = True
				if k - elem >= -llimit and (not currMap.get(k - elem)):
					currMap[k - elem] = True
			stateMap = currMap
		return 1 if stateMap.get(0) else 0


class Solution:

	def equalPartition(self, N, arr):

		def foo(i, s, dp):
			if s == 0:
				return True
			if i < 0 or s < 0:
				return False
			if dp[i][s] != -1:
				return dp[i][s]
			dp[i][s] = foo(i - 1, s - arr[i], dp) or foo(i - 1, s, dp)
			return dp[i][s]
		sm = sum(arr)
		if sm % 2 != 0:
			return 0
		dp = [[-1] * (sm // 2 + 1) for i in range(N)]
		foo(N - 1, sm // 2, dp)
		return dp[N - 1][sm // 2]


class Solution:

	def equalPartition(self, N, arr):
		sum_ = sum(arr)
		if sum_ % 2 != 0:
			return 0
		s = sum_ // 2
		dp = [[False for i in range(s + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			for j in range(s + 1):
				if i == 0 and j == 0:
					dp[i][j] = True
				elif i == 0:
					dp[i][j] = False
				elif j == 0:
					dp[i][j] = True
				elif dp[i - 1][j]:
					dp[i][j] = dp[i - 1][j]
				else:
					val = arr[i - 1]
					if j >= val:
						dp[i][j] = dp[i - 1][j - val]
		return dp[-1][-1]


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2 != 0:
			return 0
		DP = [[-1] * (total // 2 + 1) for i in range(N)]

		def reccur(index, curSum):
			if curSum == 0:
				return 1
			if index == 0:
				return int(arr[index] == curSum)
			if DP[index][curSum] != -1:
				return DP[index][curSum]
			not_take = reccur(index - 1, curSum)
			take = 0
			if curSum >= arr[index]:
				take = reccur(index - 1, curSum - arr[index])
			DP[index][curSum] = take or not_take
			return DP[index][curSum]
		return reccur(N - 1, total // 2)


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 != 0:
			return False
		t = s // 2
		d = set()
		d.add(0)
		new = []
		for i in arr:
			for j in d:
				a = i + j
				new.append(a)
			for i in new:
				d.add(i)
			new = []
			if t in d:
				return True
		if t in d:
			return True
		return False


class Solution:

	def equalPartition(self, N, arr):
		sum = 0
		for i in range(N):
			sum = sum + arr[i]
		t = [[-1 for j in range(int(sum / 2) + 1)] for i in range(N + 1)]
		if sum % 2 != 0:
			return 0
		else:
			for i in range(N + 1):
				for j in range(int(sum / 2) + 1):
					if i == 0:
						t[i][j] = 0
					if j == 0:
						t[i][j] = 1
			for i in range(1, N + 1):
				for j in range(1, int(sum / 2) + 1):
					if arr[i - 1] <= j:
						t[i][j] = t[i - 1][j - arr[i - 1]] or t[i - 1][j]
					else:
						t[i][j] = t[i - 1][j]
		return t[N][sum // 2]


def partition_sum_problem(input_arr: []):
	sum_value = sum(input_arr)
	if sum_value % 2 != 0:
		return False
	return can_partition_helper(0, int(sum_value // 2), len(input_arr) - 1, input_arr)

def can_partition_helper(index: int, remaining_sum: int, end_index, input_arr: []):
	if remaining_sum == 0:
		return True
	if index > end_index or remaining_sum < 0:
		return False
	return can_partition_helper(index + 1, remaining_sum - input_arr[index], end_index, input_arr) or can_partition_helper(index + 1, remaining_sum, end_index, input_arr)

class Solution:

	def equalPartition(self, N, arr):
		return partition_sum_problem(arr)


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2:
			return False
		s = s // 2
		part = [False] * (s + 1)
		part[0] = True
		for i in range(N):
			for j in range(s, arr[i] - 1, -1):
				if part[j - arr[i]] or j == arr[i]:
					part[j] = True
		return part[s]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def equalPartition(self, N, arr):
		if sum(arr) % 2 != 0:
			return False
		target = sum(arr) // 2

		def helper(i, n):
			if n == 0:
				return True
			if i == len(arr) or n < 0:
				return False
			return helper(i + 1, n - arr[i]) or helper(i + 1, n)
		return helper(0, target)


class Solution:

	def solve(self, arr, ind, sum, dp):
		if ind < 0:
			return sum == 0
		if dp[ind][sum] != -1:
			return dp[ind][sum]
		ans = self.solve(arr, ind - 1, sum, dp)
		if arr[ind] <= sum:
			ans = max(ans, self.solve(arr, ind - 1, sum - arr[ind], dp))
		dp[ind][sum] = ans
		return ans

	def equalPartition(self, N, arr):
		su = sum(arr)
		if su & 1 == 1:
			return 0
		dp = [[-1 for _ in range(su)] for _ in range(N)]
		return self.solve(arr, N - 1, su // 2, dp)


class Solution:

	def equalPartition(self, N, arr):
		tot = sum(arr)
		if tot % 2 == 1:
			return 0
		req = tot // 2
		allposs = set([0])
		for ele in arr:
			set2 = set()
			for sub in allposs:
				newsum = sub + ele
				if newsum == req:
					return 1
				set2.add(newsum)
			allposs = allposs.union(set2)
		return 0


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2:
			return 0
		k = total // 2
		dp = [[0 for i in range(k + 1)] for j in range(N)]
		for i in range(N):
			dp[i][0] = 1
		if arr[0] <= k:
			dp[0][arr[0]] = 1
		for i in range(1, N):
			for target in range(1, k + 1):
				nottake = dp[i - 1][target]
				take = False
				if arr[i] <= target:
					take = dp[i - 1][target - arr[i]]
				dp[i][target] = take or nottake
		return dp[N - 1][k]


class Solution:

	def equalPartition(self, N, arr):
		if len(arr) == 0:
			arr_sum = 0
		else:
			arr_sum = sum(arr)
		if arr_sum % 2 != 0:
			return 0
		dp = [[-1 for _ in range(arr_sum + 1)] for __ in range(len(arr))]
		if self.ispossible(arr, arr_sum // 2, dp, len(arr) - 1):
			return 1
		else:
			return 0

	def ispossible(self, array, rem, sub, n):
		if rem == 0:
			return True
		if n == -1 and rem != 0:
			return False
		if sub[n][rem] != -1:
			return sub[n][rem]
		if array[n] <= rem:
			not_skip = self.ispossible(array, rem - arr[n], sub, n - 1)
		else:
			not_skip = False
		skip = self.ispossible(array, rem, sub, n - 1)
		if skip or not_skip:
			sub[n][rem] = True
		else:
			sub[n][rem] = False
		return sub[n][rem]


class Solution:

	def equalPartition(self, N, arr):
		if len(arr) == 0:
			arr_sum = 0
		else:
			arr_sum = sum(arr)
		if arr_sum % 2 != 0:
			return 0
		dp = [[-1 for _ in range(arr_sum + 1)] for __ in range(len(arr))]
		return self.ispossible(arr, arr_sum // 2, dp, len(arr) - 1)

	def ispossible(self, array, rem, sub, n):
		if rem == 0:
			return 1
		if n == -1 and rem != 0:
			return 0
		if sub[n][rem] != -1:
			return sub[n][rem]
		if array[n] > rem:
			return self.ispossible(array, rem, sub, n - 1)
		if self.ispossible(array, rem - array[n], sub, n - 1) + self.ispossible(array, rem, sub, n - 1) >= 1:
			sub[n][rem] = 1
		else:
			sub[n][rem] = 0
		return sub[n][rem]


class Solution:

	def helper(self, arr, n, s, i, dp):
		if s == 0:
			return 1
		if i == n:
			return 0
		if dp[i][s] != -1:
			return dp[i][s]
		take = 0
		if arr[i] <= s:
			take = self.helper(arr, n, s - arr[i], i + 1, dp)
		nottake = self.helper(arr, n, s, i + 1, dp)
		dp[i][s] = take or nottake
		return take or nottake

	def equalPartition(self, N, arr):
		s = 0
		for i in arr:
			s += i
		p = s // 2
		if s % 2 == 1:
			return 0
		dp = [[-1 for i in range(p + 1)] for j in range(N + 1)]
		for i in range(N):
			dp[i][0] = 1
		if self.helper(arr, N, p, 0, dp):
			return 1
		return 0


class Solution:

	def equalPartition(self, N, arr):

		def come(arr, target, N):
			if target == 0:
				return True
			if N == 0:
				if arr[0] == target:
					return True
				return False
			if arr[N] <= target:
				return come(arr, target - arr[N], N - 1) or come(arr, target, N - 1)
			return come(arr, target, N - 1)
		s = 0
		for i in arr:
			s = s + i
		if s % 2 == 1:
			return False
		else:
			p = come(arr, s // 2, N - 1)
			return p


class Solution:

	def equalPartition(self, N, arr):
		dp = []
		for i in range(N):
			a = []
			for j in range(sum(arr) // 2 + 1):
				a.append(0)
			dp.append(a)
		if sum(arr) % 2 == 1:
			return 0
		for i in range(N):
			dp[i][0] = 1
		if arr[0] <= sum(arr) // 2:
			dp[0][arr[0]] = 1
		for i in range(1, N):
			for j in range(1, sum(arr) // 2 + 1):
				nottake = dp[i - 1][j]
				take = 0
				if arr[i] <= j:
					take = dp[i - 1][j - arr[i]]
				dp[i][j] = take or nottake
		return dp[N - 1][sum(arr) // 2]


class Solution:

	def equalPartition(self, N, arr):
		total = sum(arr)
		if total % 2 != 0:
			return 0
		dp = [[-1] * (total + 1) for i in range(N + 1)]

		def subset(arr, n, s, total):
			if s == total - s:
				return 1
			if n >= 0 and s == 0:
				return 0
			if n == 0 and s > 0:
				return 0
			if dp[n][s] != -1:
				return dp[n][s]
			elif arr[n - 1] <= s:
				dp[n][s] = subset(arr, n - 1, s - arr[n - 1], total) or subset(arr, n - 1, s, total)
			else:
				dp[n][s] = subset(arr, n - 1, s, total)
			return dp[n][s]
		return subset(arr, N, total, total)


class Solution:

	def equalPartition(self, N, arr):
		s = sum(arr)
		if s % 2 != 0:
			return 0
		s = s // 2 + 1
		m = [[0 for i in range(s)] for j in range(N + 1)]
		m[0][0] = 1
		for i in range(N + 1):
			for j in range(s):
				if i == 0 and j != 0:
					m[i][j] = 0
				elif j == 0:
					m[i][j] = 1
				elif arr[i - 1] > j:
					m[i][j] = m[i - 1][j]
				else:
					m[i][j] = m[i - 1][j] or m[i - 1][j - arr[i - 1]]
		return m[N][s - 1]


class Solution:

	def equalPartition(self, n, arr):
		s = sum(arr)
		if s % 2 == 1:
			return 0
		dp = [[-1] * (s // 2 + 1) for i in range(n)]

		def partpos(i, s1, s2, n):
			if s1 == s2:
				return 1
			if i >= n or s1 > s2:
				return 0
			if dp[i][s1] != -1:
				return dp[i][s1]
			inc = partpos(i + 1, s1 + arr[i], s2 - arr[i], n)
			if inc == 1:
				return 1
			ninc = partpos(i + 1, s1, s2, n)
			dp[i][s1] = 1 if inc == 1 or ninc == 1 else 0
			return 1 if inc == 1 or ninc == 1 else 0
		return partpos(0, 0, s, n)


class Solution:

	def equalPartition(self, N, arr):
		total = 0
		for i in arr:
			total += i
		dp = [[-1 for i in range(total // 2 + 1)] for j in range(N)]
		if total % 2:
			return False
		else:
			return self.recursion(0, arr, total // 2, N, dp)

	def recursion(self, idx, arr, tar, n, dp):
		if idx == n:
			if tar == 0:
				return True
			return False
		if dp[idx][tar] != -1:
			return dp[idx][tar]
		p = False
		if tar >= arr[idx]:
			p = self.recursion(idx + 1, arr, tar - arr[idx], n, dp)
		np = self.recursion(idx + 1, arr, tar, n, dp)
		dp[idx][tar] = p or np
		return dp[idx][tar]


class Solution:

	def equalPartition(self, N, arr):
		arrSum = sum(arr)
		if arrSum % 2 != 0:
			return False
		dp = dict()
		return self.subsetSum(arr, N, 0, arrSum // 2, dp)

	def subsetSum(self, arr, n, index, s, dp):
		if index == n:
			if s == 0:
				return True
			return False
		if s == 0:
			return True
		if (index, s) in dp:
			return dp[index, s]
		if arr[index] > s:
			dp[index, s] = self.subsetSum(arr, n, index + 1, s, dp)
		else:
			dp[index, s] = self.subsetSum(arr, n, index + 1, s, dp) or self.subsetSum(arr, n, index + 1, s - arr[index], dp)
		return dp[index, s]