Given an array of integers A[] of length N and an integer target.
You want to build an expression out of A by adding one of the symbols '+' and '-' before each integer in A and then concatenate all the integers.
	For example, if arr = {2, 1}, you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that can be built, which evaluates to target.
Example 1:
Input:
N = 5
A[] = {1, 1, 1, 1, 1}
target = 3
Output:
5
Explanation:
There are 5 ways to assign symbols to 
make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input:
N = 1
A[] = {1}
target = 1
Output:
1
Your Task:
The task is to complete the function findTargetSumWays() which finds and returns the number of different expressions that can be built.
 
Expected Time Complexity: O(N*sum), where sum refers to the range of sum possible.
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 20
0 ≤ A[i] ≤ 1000
0 <= sum(A[i]) <= 10^{4}
-1000 <= target <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3

class Solution:
    def findTargetSumWays(self, arr, N, target):
        # code here 

Solutions:
class Solution:

	def findTargetSumWays(self, nums, N, target):
		dp = {}
		n = len(nums)

		def helper(ind, tar):
			if ind == n and tar == target:
				return 1
			if ind == n:
				return 0
			if (ind, tar) in dp:
				return dp[ind, tar]
			take_plus = helper(ind + 1, tar - nums[ind])
			take_minus = helper(ind + 1, tar + nums[ind])
			dp[ind, tar] = take_plus + take_minus
			return dp[ind, tar]
		return helper(0, 0)


class Solution:

	def findTargetSumWays(self, nums, N, target):
		dp = {}

		def backtrack(i, total):
			if i == len(nums):
				return 1 if total == target else 0
			if (i, total) in dp:
				return dp[i, total]
			dp[i, total] = backtrack(i + 1, total + nums[i]) + backtrack(i + 1, total - nums[i])
			return dp[i, total]
		return backtrack(0, 0)
		tot = sum(arr)
		dp = [[-1 for i in range(tot + 1)] for j in range(N + 1)]

		def memo(i, sum):
			if i == N:
				if sum == target:
					return 1
				return 0
			if dp[i][target] != -1:
				return dp[i][target]
			dp[i][target] = memo(i + 1, sum + arr[i]) + memo(i + 1, sum - arr[i])
			return dp[i][target]
		return memo(0, 0)


class Solution:

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


class Solution:

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

	def solve(self, n, ts, arr, dp):
		if n == 0:
			if ts == 0 and arr[0] == 0:
				dp[n][ts] = 2
				return 2
			if ts == 0 or ts == arr[0]:
				dp[n][ts] = 1
				return 1
			dp[n][ts] = 0
			return 0
		if dp[n][ts] != -1:
			return dp[n][ts]
		pick = 0
		npick = self.solve(n - 1, ts, arr, dp)
		if arr[n] <= ts:
			pick = self.solve(n - 1, ts - arr[n], arr, dp)
		dp[n][ts] = pick + npick
		return dp[n][ts]


class Solution:

	def findTargetSumWays(self, arr, n, d):
		if n == 1 and arr[0] > d:
			return 0
		elif n == 1 and arr[0] == d:
			return 1
		(current_sum, mod) = (0, 1000000007)
		for i in arr:
			current_sum += i % mod
		if (current_sum + d) % 2 != 0 or n == 1:
			return 0
		new_sum = (current_sum + d) // 2
		dp = []
		for i in range(n + 1):
			help = [1]
			for j in range(1, new_sum + 1):
				if i == 0:
					help.append(0)
				else:
					help.append(1)
			dp.append(help)
		for i in range(1, n + 1):
			for j in range(new_sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[i][j] % mod


from functools import lru_cache

class Solution:

	def findTargetSumWays(self, nums, N, target):

		@lru_cache(None)
		def countWays(index, s):
			if index < 0 and s == 0:
				return 1
			if index < 0:
				return 0
			pos = countWays(index - 1, s + nums[index])
			neg = countWays(index - 1, s - nums[index])
			return pos + neg
		return countWays(N - 1, target)


class Solution:

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


class Solution:

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

	def findTargetSumWays(self, arr, N, target):
		if N == 0 and target != 0:
			return 0
		res = (sum(arr) + target) / 2
		if res % 1 == 0:
			res = int(res)
			return self.isSubsetSum(N, arr, res)
		return 0


class Solution:

	def findTargetSumWays(self, arr, N, target):

		def tarSum(ind, tar):
			if ind == 0:
				if arr[0] == 0 and tar == 0:
					return 2
				elif arr[0] != 0 and tar - arr[0] == 0:
					return 1
				elif arr[0] != 0 and tar + arr[0] == 0:
					return 1
				else:
					return 0
			subs = tarSum(ind - 1, tar - arr[ind])
			add = tarSum(ind - 1, tar + arr[ind])
			return subs + add
		return tarSum(N - 1, target)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		total_sum = sum(arr)
		diff = target
		if (total_sum + diff) % 2 != 0:
			return 0
		tg = (total_sum + diff) / 2
		dp = {}

		def dfs(i, s):
			if (i, s) in dp:
				return dp[i, s]
			if s == tg and i >= N:
				return 1
			if i >= N:
				return 0
			if arr[i] + s > tg:
				dp[i, s] = dfs(i + 1, s)
				return dp[i, s]
			tk = dfs(i + 1, s + arr[i])
			nt = dfs(i + 1, s)
			dp[i, s] = tk + nt
			return dp[i, s]
		return dfs(0, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		SUM = sum(arr)
		x = SUM + target
		if x % 2 != 0:
			return 0
		else:
			x = x // 2
		dp = [[0] * (x + 1) for _ in range(N)]
		for i in range(N):
			for j in range(x + 1):
				item = arr[i]
				sm = j
				if i == 0:
					if sm == 0:
						if item == 0:
							dp[i][j] = 2
						else:
							dp[i][j] = 1
					elif sm == item:
						dp[i][j] = 1
				elif item <= sm:
					dp[i][j] = dp[i - 1][sm - item] + dp[i - 1][sm]
				else:
					dp[i][j] = dp[i - 1][sm]
		return dp[N - 1][x]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		SUM = sum(arr)
		dp = {}
		arr.sort(reverse=True)
		x = SUM + target
		if x % 2 != 0:
			return 0
		else:
			x = x // 2

		def solve(n, sm):
			if n == 0:
				if sm == 0:
					return 1
				else:
					return 0
			elif (n, sm) in dp:
				return dp[n, sm]
			else:
				item = arr[n - 1]
				if item <= sm:
					c1 = solve(n - 1, sm - item)
					c2 = solve(n - 1, sm)
					c = c1 + c2
				elif sm == 0:
					c = 1
				else:
					c = 0
				dp[n, sm] = c
				return c
		return solve(N, x)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		from collections import defaultdict
		(dp1, dp2) = (defaultdict(int), defaultdict(int))
		dp1[0] = 1
		for av in arr:
			for (dv, cnt) in dp1.items():
				dp2[dv + av] += cnt
				dp2[dv - av] += cnt
			(dp1, dp2) = (dp2, dp1)
			dp2.clear()
		return dp1.get(target, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		S = sum(arr) + target
		if S % 2 != 0:
			return 0
		s1 = S // 2
		dp = [[0 for i in range(s1 + 1)] for j 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(s1 + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
		return dp[-1][-1]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		dp = {}

		def backtrack(i, total):
			if i == N:
				return 1 if total == target else 0
			if (i, total) in dp:
				return dp[i, total]
			dp[i, total] = backtrack(i + 1, total + arr[i]) + backtrack(i + 1, total - arr[i])
			return dp[i, total]
		return backtrack(0, 0)


class Solution:
	dp = []

	def gen(self, arr, n, target):
		if n < 0:
			if target == 0:
				return 1
			return 0
		if self.dp[n][target] != -1:
			return self.dp[n][target]
		l = self.gen(arr, n - 1, target - arr[n])
		r = self.gen(arr, n - 1, target + arr[n])
		self.dp[n][target] = l + r
		return l + r

	def findTargetSumWays(self, arr, N, target):
		self.dp = []
		for i in range(N):
			b = []
			for j in range(20000):
				b.append(-1)
			self.dp.append(b)
		a = self.gen(arr, N - 1, target)
		return a


class Solution:

	def findTargetSumWays(self, arr, N, target):

		def solve(i, curr, target):
			if i == 0:
				val = 0
				if curr + arr[i] == target:
					val += 1
				if curr - arr[i] == target:
					val += 1
				return val
			count = arr[i] + solve(i - 1, curr + arr[i], target) + -arr[i] + solve(i - 1, curr - arr[i], target)
			return count
		return solve(N - 1, 0, target)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		s = sum(arr)
		if s + target < 0 or (s + target) % 2:
			return 0
		t = (s + target) // 2
		dp = [0 for _ in range(t + 1)]
		dp[0] = 1
		for a in arr:
			for i in range(t, -1, -1):
				if i - a >= 0:
					dp[i] += dp[i - a]
		return dp[t]


class Solution:

	def findTargetSumWays(self, arr, N, target):

		def calc(ind, res):
			if ind == 0:
				if res + arr[0] == target and res - arr[0] == target:
					return 2
				elif res + arr[0] == target or res - arr[0] == target:
					return 1
				return 0
			pos = calc(ind - 1, res + arr[ind])
			neg = calc(ind - 1, res - arr[ind])
			return pos + neg
		return calc(N - 1, 0)


class Solution:

	def findTargetSumWays(self, nums, n, target):
		total_sum = sum(nums)
		if total_sum < target or (total_sum + target) % 2 == 1:
			return 0
		s = (total_sum + target) // 2
		dp = [0] * (s + 1)
		dp[0] = 1
		for i in range(n):
			for j in range(s, nums[i] - 1, -1):
				dp[j] += dp[j - nums[i]]
		return dp[s]


class Solution:

	def findTargetSumWays(self, nums, N, target):
		dp = {}

		def dfs(index=0, total=0):
			if index == len(nums):
				return 1 if total == target else 0
			if (index, total) in dp:
				return dp[index, total]
			dp[index, total] = dfs(index + 1, total - nums[index]) + dfs(index + 1, total + nums[index])
			return dp[index, total]
		return dfs()


class Solution:

	def SubSumcount(self, arr, sum, N):
		t = [[-1 for _ in range(sum + 1)] for _ in range(N + 1)]
		for i in range(N + 1):
			for j in range(sum + 1):
				if i == 0:
					t[i][j] = 0
		for i in range(N + 1):
			for j in range(sum + 1):
				if j == 0:
					t[i][j] = 1
		for i in range(1, N + 1):
			for j in range(sum + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[N][sum]

	def findTargetSumWays(self, arr, N, target):
		Sum = sum(arr)
		news = (target + Sum) / 2
		if news - int(news) != 0:
			return 0
		return self.SubSumcount(arr, int(news), N)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		memo = {}

		def dp(i, j):
			if j == 0 and i == -1:
				return 1
			if i == 0:
				ans = 0
				if j - arr[0] == 0:
					ans += 1
				if j + arr[0] == 0:
					ans += 1
				return ans
			ans = dp(i - 1, j - arr[i]) + dp(i - 1, j + arr[i])
			memo[i, j] = ans
			return ans
		return dp(N - 1, target)


class Solution:

	def findTargetSumWays(self, arr, n, d):
		target = 0
		for el in arr:
			target += el
		target -= d
		if target % 2 != 0 or target < 0:
			return 0
		target = target // 2
		dp = [[0 for _ in range(target + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for index in range(n - 1, -1, -1):
			for j in range(target + 1):
				inc = 0
				if j - arr[index] >= 0:
					inc = dp[index + 1][j - arr[index]]
				exc = dp[index + 1][j]
				dp[index][j] = inc + exc
		return dp[0][target]


class Solution:

	def findTargetSumWays(self, nums, N, target):

		def backtrack(total, index, memo):
			if (index, total) in memo:
				return memo[index, total]
			if total == target and index == len(nums):
				return 1
			elif index >= len(nums):
				return 0
			memo[index, total] = backtrack(total + nums[index], index + 1, memo) + backtrack(total - nums[index], index + 1, memo)
			return memo[index, total]
		return backtrack(0, 0, {})


class Solution:

	def findTargetSumWays(self, arr, N, target):
		sum1 = 0
		for i in arr:
			sum1 += i
		if sum1 - target < 0 or (sum1 - target) % 2 == 1:
			return 0
		s2 = (sum1 - target) // 2
		dp = [[0 for i in range(s2 + 1)] for j in range(N)]
		if arr[0] == 0:
			dp[0][0] = 2
		else:
			dp[0][0] = 1
		if arr[0] != 0 and arr[0] <= s2:
			dp[0][arr[0]] = 1
		for i in range(1, N):
			for j in range(s2 + 1):
				take = 0
				if arr[i] <= j:
					take = dp[i - 1][j - arr[i]]
				notTake = dp[i - 1][j]
				dp[i][j] = take + notTake
		return dp[N - 1][s2]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		k = sum(arr)
		if (k - target) % 2 == 1 or k < target:
			return 0
		mn = (k - target) // 2
		dp = [[0] * (mn + 1) for _ in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(mn + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		sm = sum(arr)
		if sm + target < 0 or (sm + target) % 2:
			return 0
		sub = (sm + target) // 2
		t = [[-1 for i in range(sub + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			for j in range(sub + 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(0, sub + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[N][sub]


class Solution:

	def countPartitions(self, n, d, arr):
		tot = sum(arr)
		target = (tot - d) // 2
		if (tot - d) % 2 or tot - d < 0:
			return 0
		memo = [[-1] * (tot + 1) for _ in range(n)]
		return self.sumCount(0, arr, n, target, memo)

	def sumCount(self, i, nums, n, target, memo):
		if i == n:
			if target == 0:
				return 1
			return 0
		if memo[i][target] == -1:
			MOD = 10 ** 9 + 7
			take = 0
			not_take = self.sumCount(i + 1, nums, n, target, memo)
			if nums[i] <= target:
				take = self.sumCount(i + 1, nums, n, target - nums[i], memo)
			memo[i][target] = (take + not_take) % MOD
		return memo[i][target]

	def findTargetSumWays(self, arr, N, target):
		return self.countPartitions(len(arr), target, arr)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		total = sum(arr)
		if (total - target) % 2 == 1 or total < target:
			return 0
		s = (total - target) // 2
		t = [[0 for _ in range(s + 1)] for _ in range(N + 1)]
		t[0][0] = 1
		for i in range(1, N + 1):
			for j in range(s + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[N][s]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		dic = {}

		def backtracking(ind, sum):
			if ind == len(arr):
				if sum == target:
					return 1
				else:
					return 0
			if (ind, sum) in dic:
				return dic[ind, sum]
			dic[ind, sum] = backtracking(ind + 1, sum + arr[ind]) + backtracking(ind + 1, sum - arr[ind])
			return dic[ind, sum]
		return backtracking(0, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		totalsum = 0
		for i in range(0, N):
			totalsum += arr[i]
		if totalsum - target < 0:
			return 0
		if (totalsum - target) % 2 == 1:
			return 0
		s2 = (totalsum - target) // 2
		dp = [[-1 for i in range(s2 + 1)] for j in range(N + 1)]
		return self.helper(N - 1, s2, arr, dp)

	def helper(self, ind, target, nums, dp):
		if ind == 0:
			if target == 0 and nums[0] == 0:
				return 2
			if target == 0 or nums[0] == target:
				return 1
			return 0
		if dp[ind][target] != -1:
			return dp[ind][target]
		notpick = self.helper(ind - 1, target, nums, dp)
		pick = 0
		if nums[ind] <= target:
			pick = self.helper(ind - 1, target - nums[ind], nums, dp)
		dp[ind][target] = pick + notpick
		return dp[ind][target]


class Solution:

	def findTargetSumWays(self, arr, N, target):

		def helper(arr, N, s1, l):
			if N == 0 and s1 == 0:
				return 1
			if N == 0:
				return 0
			if l[N][s1] != -1:
				return l[N][s1]
			if arr[N - 1] <= s1:
				l[N][s1] = helper(arr, N - 1, s1 - arr[N - 1], l) + helper(arr, N - 1, s1, l)
				return l[N][s1]
			else:
				l[N][s1] = helper(arr, N - 1, s1, l)
				return l[N][s1]
		s = sum(arr)
		if (s + target) % 2 != 0:
			return 0
		s1 = (s + target) // 2
		l = [[-1 for i in range(s1 + 1)] for j in range(N + 1)]
		ans = helper(arr, N, s1, l)
		return ans


class Solution:

	def fun(self, idx, target, arr, dp):
		if idx == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or arr[0] == target:
				return 1
			else:
				return 0
		if dp[idx][target] != -1:
			return dp[idx][target]
		np = self.fun(idx - 1, target, arr, dp)
		p = 0
		if arr[idx] <= target:
			p = self.fun(idx - 1, target - arr[idx], arr, dp)
		dp[idx][target] = p + np
		return dp[idx][target]

	def findTargetSumWays(self, arr, n, d):
		total = sum(arr)
		target = (total - d) // 2
		if total - d < 0 or (total - d) % 2 == 1:
			return 0
		else:
			dp = [[0 for i in range(target + 1)] for j in range(n)]
			if arr[0] == 0:
				dp[0][0] = 2
			else:
				dp[0][0] = 1
			if arr[0] != 0 and arr[0] <= target:
				dp[0][arr[0]] = 1
			for i in range(1, n):
				for t in range(target + 1):
					np = dp[i - 1][t]
					p = 0
					if arr[i] <= t:
						p = dp[i - 1][t - arr[i]]
					dp[i][t] = p + np
			return dp[n - 1][target]


class Solution:

	def findTargetSumWays1(self, N, arr, sum):
		t = [[-1 for j in range(sum + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			for j in range(sum + 1):
				if i == 0:
					t[i][j] = 0
				if j == 0:
					t[i][j] = 1
		for i in range(N):
			for j in range(sum + 1):
				if j >= arr[i]:
					t[i + 1][j] = t[i][j - arr[i]] + t[i][j]
				else:
					t[i + 1][j] = t[i][j]
		return t

	def findTargetSumWays(self, arr, N, target):
		s = (target + sum(arr)) // 2
		if (target + sum(arr)) % 2 == 0:
			t = self.findTargetSumWays1(N, arr, s)
			return t[N][s]
		return 0


class Solution:

	def fun(self, idx, target, arr):
		if idx == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or arr[0] == target:
				return 1
			else:
				return 0
		np = self.fun(idx - 1, target, arr)
		p = 0
		if arr[idx] <= target:
			p = self.fun(idx - 1, target - arr[idx], arr)
		return p + np

	def findTargetSumWays(self, arr, n, d):
		total = sum(arr)
		target = (total - d) // 2
		if total - d < 0 or (total - d) % 2 == 1:
			return 0
		else:
			return self.fun(n - 1, target, arr)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		totasum = sum(arr)
		if totasum - target < 0 or (totasum - target) % 2 == 1:
			return 0
		s2 = (totasum - target) // 2
		return countpartition(arr, s2)

def countpartition(arr, target):
	n = len(arr)
	prev = [0] * (target + 1)
	if arr[0] == 0:
		prev[0] = 2
	else:
		prev[0] = 1
	if arr[0] != 0 and arr[0] <= target:
		prev[arr[0]] = 1
	for ind in range(1, n):
		curr = [0] * (target + 1)
		for tar in range(target + 1):
			notpick = 0 + prev[tar]
			pick = 0
			if arr[ind] <= tar:
				pick = prev[tar - arr[ind]]
			curr[tar] = pick + notpick
		prev = curr
	return prev[target]


class Solution:

	def ways(self, arr, target):
		n = len(arr)
		dp = [[0] * (target + 1) for i in range(len(arr) + 1)]
		dp[0][0] = 1
		for j in range(1, target + 1):
			dp[0][j] = 0
		for i in range(1, len(arr) + 1):
			for t in range(target + 1):
				nottake = dp[i - 1][t]
				take = 0
				if t >= arr[i - 1]:
					take = dp[i - 1][t - arr[i - 1]]
				dp[i][t] = take + nottake
		return dp[n][target]

	def countPartitions(self, n, d, arr):
		totsum = sum(arr)
		if totsum - d < 0 or (totsum - d) % 2 != 0:
			return 0
		return self.ways(arr, (totsum - d) // 2)

	def findTargetSumWays(self, arr, N, target):
		return self.countPartitions(N, target, arr)


class Solution:

	def subset(self, arr, ind, target, dp):
		if ind == 0:
			if target == 0 and arr[0] == 0:
				return 2
			if target == 0 or arr[0] == target:
				return 1
			return 0
		if dp[ind][target] != -1:
			return dp[ind][target]
		nottake = self.subset(arr, ind - 1, target, dp)
		take = 0
		if target >= arr[ind]:
			take = self.subset(arr, ind - 1, target - arr[ind], dp)
		dp[ind][target] = take + nottake
		return dp[ind][target]

	def ways(self, arr, tar):
		n = len(arr)
		dp = [[-1] * (tar + 1) for i in range(len(arr))]
		return self.subset(arr, n - 1, tar, dp)

	def countPartitions(self, n, d, arr):
		totsum = sum(arr)
		if totsum - d < 0 or (totsum - d) % 2 != 0:
			return 0
		return self.ways(arr, (totsum - d) // 2)

	def findTargetSumWays(self, arr, N, target):
		return self.countPartitions(N, target, arr)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		dp = {}

		def f(ind, total):
			if ind == N:
				return target == total
			if (ind, total) in dp:
				return dp[ind, total]
			dp[ind, total] = f(ind + 1, total + arr[ind]) + f(ind + 1, total - arr[ind])
			return dp[ind, total]
		return f(0, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		dp = {}

		def dfs(i, total):
			if i == N and total == target:
				return 1
			if i == N:
				return 0
			if (i, total) in dp:
				return dp[i, total]
			dp[i, total] = dfs(i + 1, total + arr[i]) + dfs(i + 1, total - arr[i])
			return dp[i, total]
		return dfs(0, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		nums = arr
		s = sum(nums) + target
		if s & 1 == 1:
			return 0
		newTarget = s // 2
		if abs(target) > sum(nums):
			return 0
		dp = [[-1 for i in range(newTarget + 1)] for j in range(len(nums) + 1)]
		for i in range(newTarget + 1):
			dp[0][i] = 0
		for i in range(len(nums) + 1):
			dp[i][0] = 1
		for i in range(1, len(nums) + 1):
			for j in range(newTarget + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(nums)][newTarget]


import sys
sys.setrecursionlimit(50000)

class Solution:

	def recur(self, i, target, arr, dp, total, diff):
		if i == 0:
			if target - arr[0] == 0 or target + arr[0] == 0:
				if arr[0] == 0:
					return 2
				else:
					return 1
			else:
				return 0
		if dp[i][total + target - diff] != -1:
			return dp[i][total + target - diff]
		minus = self.recur(i - 1, target + arr[i], arr, dp, total, diff)
		plus = self.recur(i - 1, target - arr[i], arr, dp, total, diff)
		dp[i][total + target - diff] = minus + plus
		return minus + plus

	def findTargetSumWays(self, arr, N, target):
		total = sum(arr)
		diff = target
		dp = [[-1 for i in range(total * 2 + 1)] for j in range(N)]
		return self.recur(N - 1, target, arr, dp, total, diff)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		sm = sum(arr)
		x = sm + target
		if x % 2 != 0:
			return 0
		else:
			x = (sm + target) // 2
		dp = {}
		arr.sort(reverse=True)

		def aa(n, smm):
			if n == 0:
				if smm == 0:
					return 1
				else:
					return 0
			elif (n, sm) in dp:
				return dp[n, sm]
			else:
				val = arr[n - 1]
				if val <= smm:
					c1 = aa(n - 1, smm - val)
					c2 = aa(n - 1, smm)
					c = c1 + c2
				elif smm == 0:
					c = 1
				else:
					c = 0
				dp[n, smm] = c
				return c
		return aa(N, x)


class Solution:

	def findTargetSumWays(self, nums, N, target):
		W = sum(nums)
		if N == 1:
			if abs(nums[0]) == abs(target):
				return 1
			else:
				return 0
		if (W + target) % 2 != 0 or W < target:
			return 0
		W = (W + target) // 2
		t = [[0 for i in range(W + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			t[i][0] = 1
		for n in range(1, N + 1):
			for w in range(W + 1):
				if nums[n - 1] <= w:
					t[n][w] = t[n - 1][w] + t[n - 1][w - nums[n - 1]]
				else:
					t[n][w] = t[n - 1][w]
		return t[N][W]


class Solution:

	def findTargetSumWays(self, nums, N, target):
		from functools import lru_cache

		@lru_cache(None)
		def rec(index, cur):
			if index == len(nums):
				if cur == target:
					return 1
				return 0
			return rec(index + 1, cur + nums[index]) + rec(index + 1, cur - nums[index])
		return rec(0, 0)


class Solution:

	def findTargetSumWays(self, wt, N, target):
		Sum = sum(wt)
		W = (Sum + target) // 2
		if (Sum + target) % 2 != 0:
			return 0
		dp = [[0 for i 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
		for i in range(1, N + 1):
			for j in range(W + 1):
				if j >= wt[i - 1]:
					dp[i][j] = dp[i - 1][j - wt[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[N][W]


class Solution:

	def f(self, arr, ind, tar, dp):
		if ind == -1:
			if tar == 0:
				return 1
			return 0
		if tar in dp[ind]:
			return dp[ind][tar]
		pos = self.f(arr, ind - 1, tar - arr[ind], dp)
		neg = self.f(arr, ind - 1, tar + arr[ind], dp)
		dp[ind][tar] = pos + neg
		return pos + neg

	def findTargetSumWays(self, arr, N, target):
		dp = []
		for i in range(N):
			dp.append(dict())
		return self.f(arr, N - 1, target, dp)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		total = sum(arr)
		if total < target or (total - target) % 2:
			return 0
		return self.findways(arr, (total - target) // 2)

	def findways(self, arr, target):
		n = len(arr)
		dp = [[0 for i in range(target + 1)] for j in range(n)]
		if arr[0] == 0:
			dp[0][0] = 2
		else:
			dp[0][0] = 1
		if arr[0] <= target and arr[0] != 0:
			dp[0][arr[0]] = 1
		for i in range(1, n):
			for j in range(target + 1):
				not_taken = dp[i - 1][j]
				taken = 0
				if arr[i] <= j:
					taken = dp[i - 1][j - arr[i]]
				dp[i][j] = taken + not_taken
		return dp[n - 1][target]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		hashTable = {}

		def Helper(index, total):
			if index >= len(arr):
				if total == target:
					return 1
				return 0
			if (index, total) in hashTable:
				return hashTable[index, total]
			plus = Helper(index + 1, total + arr[index])
			minus = Helper(index + 1, total - arr[index])
			hashTable[index, total] = plus + minus
			return hashTable[index, total]
		return Helper(0, 0)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		t = target
		tsum = sum(arr)
		if target > tsum:
			return 0
		if (target + tsum) % 2 != 0:
			return 0
		res = (tsum + target) // 2
		target = res
		dparr = [[0] * (target + 1) for i in range(N + 1)]
		if len(dparr) <= 0 or len(dparr[0]) == 0:
			return 0
		for i in range(N + 1):
			if i == 0:
				dparr[i][0] = 1
		for i in range(1, N + 1):
			for j in range(target + 1):
				if arr[i - 1] > j:
					dparr[i][j] = dparr[i - 1][j]
				else:
					dparr[i][j] = dparr[i - 1][j] + dparr[i - 1][j - arr[i - 1]]
		return dparr[N][target]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		nums = arr

		def recursive_call(val, index, mem={}):
			if val == target and index == len(nums):
				return 1
			if index > len(nums) - 1:
				return 0
			if (index, val) in mem:
				return mem[index, val]
			else:
				curr_val = nums[index]
				plus = recursive_call(val + curr_val, index + 1)
				minus = recursive_call(val + -1 * curr_val, index + 1)
				result = plus + minus
				mem[index, val] = result
				return result
		return recursive_call(0, 0)


class Solution:

	def findTargetSumWays(self, arr, n, d):
		tot = sum(arr)
		x = (tot - d) // 2
		if tot - d < 0 or (tot - d) % 2:
			return 0
		dp = [[0] * (x + 1) for _ in range(n)]
		if arr[0] == 0:
			dp[0][0] = 2
		else:
			dp[0][0] = 1
		if arr[0] != 0 and arr[0] <= x:
			dp[0][arr[0]] = 1
		for idx in range(1, n):
			for s in range(x + 1):
				notTake = dp[idx - 1][s]
				take = 0
				if arr[idx] <= s:
					take = dp[idx - 1][s - arr[idx]]
				dp[idx][s] = notTake + take
		return dp[n - 1][x]


class Solution:

	def count(self, arr, n, x):
		t = [[0 for i in range(x + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			t[i][0] = 1
		for i in range(1, n + 1):
			for j in range(x + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] + t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[n][x]

	def findTargetSumWays(self, arr, N, target):
		s = sum(arr)
		if target > s:
			return 0
		if (s + target) % 2 != 0:
			return 0
		x = (s + target) // 2
		return self.count(arr, N, x)


class Solution:

	def findTargetSumWays(self, arr, N, target):
		totalSum = 0
		for i in range(N):
			totalSum += arr[i]
		if totalSum < target or (totalSum - target) % 2:
			return 0
		tar = (totalSum - target) // 2
		dp = [[0 for i in range(tar + 1)] for j in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(tar + 1):
				dp[i][j] = dp[i - 1][j]
				if j >= arr[i - 1]:
					dp[i][j] = dp[i][j] + dp[i - 1][j - arr[i - 1]]
		return dp[N][tar]


class Solution:

	def findTargetSumWays(self, wt, n, target):
		Sum = sum(wt)
		if (target + Sum) % 2:
			return 0
		W = (target + Sum) // 2
		dp = [[0 for i 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
		wt.sort(reverse=True)
		for i in range(1, n + 1):
			for j in range(W + 1):
				if wt[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - wt[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][W]


class Solution:

	def findTargetSumWays(self, arr, n, d):
		x = sum(arr)
		min1 = (d + sum(arr)) // 2
		if x == 0 and d == 0:
			return 2 ** len(arr)
		if x + d < 0 or (x + d) % 2 == 1:
			return 0
		t = [[None for j in range(min1 + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(min1 + 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(min1 + 1):
				if j >= arr[i - 1]:
					t[i][j] = (t[i - 1][j] + t[i - 1][j - arr[i - 1]]) % 1000000007
				else:
					t[i][j] = t[i - 1][j]
		return t[n][min1]


class Solution:

	def findTargetSumWays(self, arr, N, target):
		target = sum(arr) - target
		if target < 0 or target % 2 == 1:
			return 0
		target //= 2
		n = len(arr)
		dp = [[-1] * (target + 1) for _ in range(n)]

		def f(n, s):
			if n == 0:
				if s == 0 and arr[n] == 0:
					return 2
				if s == 0 or arr[n] == s:
					return 1
				return 0
			if dp[n][s] != -1:
				return dp[n][s]
			pick = 0
			if arr[n] <= s:
				pick = f(n - 1, s - arr[n])
			notPick = f(n - 1, s)
			dp[n][s] = pick + notPick
			return dp[n][s]
		return f(n - 1, target)


class Solution:

	def findTargetSumWays(self, arr, N, target):

		def solve(n, s):
			if n == 0:
				if s == 0 and arr[n] == 0:
					return 2
				if arr[n] == abs(s):
					return 1
				return 0
			if (n, s) in dp:
				return dp[n, s]
			pick = solve(n - 1, s - arr[n])
			notPick = solve(n - 1, s + arr[n])
			dp[n, s] = pick + notPick
			return dp[n, s]
		dp = {}
		return solve(N - 1, target)


class Solution:

	def findTargetSumWays(self, arr, n, target):
		dp = [[-1 for i in range(100000)] for _ in range(n + 1)]

		def helper(i, summ):
			if i == n:
				return target == summ
			if dp[i][summ] != -1:
				return dp[i][summ]
			negative = helper(i + 1, summ - arr[i])
			positive = helper(i + 1, summ + arr[i])
			dp[i][summ] = negative + positive
			return dp[i][summ]
		return helper(0, 0)