Given an array arr of size n containing non-negative integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference
Example 1:
Input: N = 4, arr[] = {1, 6, 11, 5} 
Output: 1
Explanation: 
Subset1 = {1, 5, 6}, sum of Subset1 = 12 
Subset2 = {11}, sum of Subset2 = 11   
Example 2:
Input: N = 2, arr[] = {1, 4}
Output: 3
Explanation: 
Subset1 = {1}, sum of Subset1 = 1
Subset2 = {4}, sum of Subset2 = 4
Your Task:  
You don't need to read input or print anything. Complete the function minDifference() which takes N and array arr as input parameters and returns the integer value
Expected Time Complexity: O(N*|sum of array elements|)
Expected Auxiliary Space: O(N*|sum of array elements|)
Constraints:
1 ≤ N*|sum of array elements| ≤ 10^{6}
0 < arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def minDifference(self, arr, n):

		# code here

Solutions:
class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		dp = [[False for j in range(s + 1)] for i in range(n)]
		for i in range(n):
			dp[i][0] = True
		dp[0][arr[0]] = True
		for i in range(1, n):
			for j in range(1, s + 1):
				not_take = dp[i - 1][j]
				take = False
				if arr[i] <= j:
					take = dp[i - 1][j - arr[i]]
				dp[i][j] = not_take | take
		t = []
		mini = 1000000000.0
		for i in range(s + 1):
			if dp[n - 1][i] == True:
				t.append(i)
		for i in range(len(t)):
			mini = min(mini, abs(s - 2 * t[i]))
		return mini


class Solution:

	def minDifference(self, arr, n):
		total = sum(arr)
		dp = [[False for i in range(total + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(total + 1):
				if j == 0:
					dp[i][j] = True
				elif 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]
		r_total = total // 2
		res = 9999999
		for i in range(r_total + 1):
			if dp[n][i]:
				res = min(res, abs(2 * i - total))
		return res


class Solution:

	def minDifference(self, arr, n):
		SUM = sum(arr)
		dp = {}

		def solve(n, p1, SUM):
			p2 = SUM - p1
			if n == 0:
				return p1 - p2
			elif (n, p1) in dp:
				return dp[n, p1]
			else:
				item = arr[n - 1]
				if p1 - item >= p2 + item:
					c1 = solve(n - 1, p1 - item, SUM)
					c2 = solve(n - 1, p1, SUM)
					c = min(c1, c2)
				else:
					c = solve(n - 1, p1, SUM)
				dp[n, p1] = c
				return c
		return solve(N, SUM, SUM)


class Solution:

	def minDifference(self, arr, n):
		rangeMax = sum(arr)

		def findSubsetSum(arr, n, sumRange):
			dp = [[False for x in range(sumRange + 1)] for x in range(n + 1)]
			for i in range(0, n + 1):
				dp[i][0] = True
			for i in range(1, n + 1):
				for j in range(1, sumRange + 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]
		subsetSums = findSubsetSum(arr, n, rangeMax)
		mn = rangeMax
		for i in range(rangeMax // 2 + 1):
			if subsetSums[i] == True:
				mn = min(mn, rangeMax - 2 * i)
		return mn


class Solution:

	def minDifference(self, arr, n):
		total = sum(arr)
		max_req = total // 2 + 1
		sum_possible = [False] * (total // 2 + 1)
		temp = [False] * (total // 2 + 1)
		sum_possible[0] = True
		for i in range(n):
			for j in range(total // 2 + 1):
				if sum_possible[j] and j + arr[i] <= total // 2:
					temp[j + arr[i]] = True
			for j in range(len(temp)):
				sum_possible[j] |= temp[j]
				temp[j] = False
		for s in range(total // 2, -1, -1):
			if sum_possible[s]:
				return total - s - s
		return 0


class Solution:

	def minDifference(self, arr, n):
		(totalSum, res) = (sum(arr), 1000000000.0)
		prev = [False] * (totalSum + 1)
		prev[0] = True
		if arr[0] <= totalSum:
			prev[arr[0]] = True
		for i in range(1, n):
			cur = [False] * (totalSum + 1)
			cur[0] = True
			for target in range(1, totalSum + 1):
				not_pick = prev[target]
				pick = False
				if arr[i] <= target:
					pick = prev[target - arr[i]]
				cur[target] = not_pick or pick
			prev = cur
		for s1 in range(totalSum // 2 + 1):
			if prev[s1]:
				s2 = totalSum - s1
				res = min(res, abs(s1 - s2))
		return res


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		dp = [[-1 for i in range(s + 1)] for j in range(n + 1)]

		def dfs(i, target):
			if target == 0:
				return True
			if i < 0 or target < 0:
				return False
			if dp[i][target] != -1:
				return dp[i][target]
			dp[i][target] = dfs(i - 1, target - arr[i]) or dfs(i - 1, target)
			return dp[i][target]
		for i in range(s + 1):
			dummy = dfs(n - 1, i)
		res = float('inf')
		for i in range(s + 1):
			if dp[n - 1][i] == True:
				res = min(res, abs(i - (s - i)))
		return res


class Solution:

	def minDifference(self, arr, n):
		k = sum(arr)
		l = [[0 for _ in range(k + 1)] for x in range(n + 1)]
		for i in range(n + 1):
			for j in range(k + 1):
				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, k + 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]
		for i in range((k + 1) // 2 + 1):
			if l[n][i]:
				result = abs(k - 2 * i)
		return result


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		t = [[-1] * (s + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(s + 1):
				if i == 0:
					t[i][j] = 0
				if j == 0:
					t[i][j] = 1
				if i > 0 and j > 0:
					pick = 0
					if j >= arr[i - 1]:
						pick = t[i - 1][j - arr[i - 1]]
					non_pick = t[i - 1][j]
					t[i][j] = pick or non_pick
		res = 0
		for i in range(s // 2 + 1):
			if t[-1][i] == 1:
				res = i
		return s - 2 * res


class Solution:

	def minDifference(self, arr, n):
		sumi = sum(arr)
		res = [[0 for _ in range(sumi + 1)] for x in range(n + 1)]
		for i in range(n + 1):
			for j in range(sumi + 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, sumi + 1):
				if arr[i - 1] <= j:
					res[i][j] = res[i - 1][j] or res[i - 1][j - arr[i - 1]]
				else:
					res[i][j] = res[i - 1][j]
		for i in range((sumi + 1) // 2 + 1):
			if res[n][i]:
				result = abs(sumi - 2 * i)
		return result


class Solution:

	def minDifference(self, nums, n):
		n = len(nums)
		target_sum = sum(nums)
		dp = [[False for _ in range(target_sum + 1)] for _ in range(n + 1)]
		dp[0][0] = True
		for i in range(1, n + 1):
			for j in range(target_sum + 1):
				if j < nums[i - 1]:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
		mi = float('inf')
		for i in range(target_sum // 2 + 1):
			if dp[n][i]:
				mi = min(mi, target_sum - 2 * i)
		return mi


import sys

class Solution:

	def minDifference(self, arr, n):
		sum = 0
		for i in arr:
			sum += i
		t = [[False for i in range(sum + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			t[i][0] = True
		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] or t[i - 1][j - arr[i - 1]]
				else:
					t[i][j] = t[i - 1][j]
		diff = sys.maxsize
		for j in range(sum // 2, -1, -1):
			if t[n][j] == True:
				diff = sum - 2 * j
				break
		return diff


class Solution:

	def minDifference(self, arr, n):
		sum_ = sum(arr)
		dp = [False] * (sum_ + 1)
		dp[0] = True
		for element in arr:
			for j in range(sum_, element - 1, -1):
				if dp[j - element]:
					dp[j] = True
		miniDiff = float('inf')
		for i in range(sum_ + 1):
			if dp[i] == False:
				continue
			first = i
			second = sum_ - first
			miniDiff = min(miniDiff, abs(first - second))
		return miniDiff


class Solution:
	mini = 999999999
	dp = []

	def gen(self, arr, n, suma, g):
		cmp = abs(suma - (g - suma))
		if n == 0:
			if self.mini > cmp:
				self.mini = cmp
			self.dp[n][suma] = self.mini
			return self.mini
		if self.dp[n][suma] != -1:
			return self.dp[n][suma]
		if self.mini > cmp:
			self.mini = cmp
		l = self.gen(arr, n - 1, suma + arr[n], g)
		r = self.gen(arr, n - 1, suma, g)
		self.dp[n][suma] = min(l, r)
		return min(l, r)

	def minDifference(self, arr, n):
		self.dp = []
		g = sum(arr)
		for i in range(n + 1):
			a = []
			for j in range(g + 1):
				a.append(-1)
			self.dp.append(a)
		self.mini = 999999999
		a = self.gen(arr, n - 1, 0, g)
		return a


class Solution:

	def minDifference(self, arr, n):
		n = len(arr)
		target = sum(arr)
		dp = [[False] * (sum(arr) + 1) for i in range(n)]
		for i in range(n):
			dp[i][0] = True
		if arr[0] <= target:
			dp[0][arr[0]] = True
		for i in range(1, n):
			for tg in range(1, target + 1):
				nt = dp[i - 1][tg]
				t = False
				if target >= arr[i]:
					t = dp[i - 1][tg - arr[i]]
				dp[i][tg] = nt or t
		mini = int(1000000000.0)
		for i in range(sum(arr) + 1):
			if dp[n - 1][i] == True:
				diff = abs(i - (sum(arr) - i))
				mini = min(mini, diff)
		return mini


class Solution:

	def minDifference(self, arr, n):
		if n == 1:
			return arr[0]
		ran = sum(arr)
		s1 = ran // 2
		dp = [[False for x in range(s1 + 1)] for _ 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, s1 + 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]
		ans = float('inf')
		for i in range(1, s1 + 1):
			if dp[n][i] == True:
				pk = ran - 2 * i
				ans = min(ans, pk)
		return ans


class Solution:

	def minDifference(self, arr, n):
		sum = 0
		for i in arr:
			sum += i
		sum1 = sum // 2
		K = [[0 for x in range(sum1 + 1)] for x in range(N + 1)]
		for i in range(N + 1):
			for j in range(sum1 + 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]
		li = []
		for i in range(sum1 + 1):
			if K[N][i] == True:
				li.append(i)
		mini = float('inf')
		for i in li:
			if sum - 2 * i < mini:
				mini = sum - 2 * i
		return mini


def minimumDiff(arr, dp, n, m):
	for i in range(1, n + 1):
		for j in range(1, m + 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]

class Solution:

	def minDifference(self, arr, n):
		m = sum(arr)
		dp = [[False for _ in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		minimumDiff(arr, dp, n, m)
		ans = []
		for i in range(m // 2 + 1):
			if dp[n][i] == True:
				ans.append(i)
		res = float('inf')
		for i in range(len(ans)):
			res = min(res, m - 2 * ans[i])
		return res


class Solution:

	def minDifference(self, arr, n):
		if n == 1:
			return arr[0]
		if n == 2:
			return abs(arr[0] - arr[1])
		sum_ = sum(arr)
		min_ = max(arr)
		dif = sum_ - min_
		if n == 3:
			return abs(sum_ - 2 * max(arr))
		dp = [[0 for i in range(dif + 1)] for j in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(dif + 1):
				if dp[i - 1][abs(arr[i - 1] - j)] == 1:
					dp[i][j] = 1
				if abs(arr[i - 1] + j) < dif + 1 and dp[i - 1][abs(arr[i - 1] + j)] == 1:
					dp[i][j] = 1
		ans = 9999999999999
		for i in range(dif + 1):
			if dp[-1][i] == 1:
				return min(ans, i)
		return ans


from collections import defaultdict

class Solution:

	def minDifference(self, nums, n):
		s = sum(nums)
		dp = [False for i in range(s + 1)]
		dp[0] = True
		for i in range(1, len(nums)):
			temp = [False for i in range(s + 1)]
			temp[0] = True
			for j in range(1, s + 1):
				if nums[i] > j:
					temp[j] = dp[j]
				else:
					temp[j] = dp[j] or dp[j - nums[i]]
			dp = temp
		m = float('inf')
		for i in range(s + 1):
			if dp[i]:
				m = min(m, abs(2 * i - s))
		return m


import sys

class Solution:

	def minDifference(self, nums, size):
		totalsum = 0
		for num in nums:
			totalsum += num
		dp = [[False for i in range(totalsum + 1)] for j in range(size)]
		if nums[0] <= totalsum:
			dp[0][totalsum] = True
		for i in range(size):
			dp[i][0] = True
		for i in range(1, size):
			for j in range(1, totalsum + 1):
				notpick = dp[i - 1][j]
				pick = False
				if nums[i] <= j:
					pick = dp[i - 1][j - nums[i]]
				dp[i][j] = pick or notpick
		ans = sys.maxsize
		for target in range(totalsum + 1):
			secondtarget = 0
			if dp[size - 1][target]:
				secondtarget = totalsum - target
				ans = min(abs(secondtarget - target), ans)
		return ans


class Solution:

	def minDifference(self, arr, n):
		total = 0
		for i in arr:
			total += i
		dp = [[False for _ in range(total + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, total + 1):
			dp[0][i] = False
		for i in range(1, n + 1):
			for j in range(1, total + 1):
				dp[i][j] = dp[i - 1][j] or (dp[i - 1][j - arr[i - 1]] if j - arr[i - 1] >= 0 else False)
		minimum = float('inf')
		for i in range(total + 1):
			if dp[n][i] == True:
				minimum = min(minimum, abs(total - 2 * i))
		return minimum


class Solution:

	def minDifference(self, arr, n):
		dic = dict()
		x = self.solve(arr, n - 1, 0, 0, dic)
		return x

	def solve(self, S, n, S1, S2, lookup):
		if n < 0:
			return abs(S1 - S2)
		key = (n, S1)
		if key not in lookup:
			inc = self.solve(S, n - 1, S1 + S[n], S2, lookup)
			exc = self.solve(S, n - 1, S1, S2 + S[n], lookup)
			lookup[key] = min(inc, exc)
		return lookup[key]


class Solution:

	def minDifference(self, nums, n):
		n = len(nums)
		Sum = sum(nums)
		dp = [[False for i in range(Sum + 1)] for i in range(n)]
		target = Sum
		for i in range(n):
			dp[i][0] = True
		if target == nums[0]:
			dp[0][0] = True
		for i in range(1, n):
			for j in range(1, Sum + 1):
				nottake = dp[i - 1][j]
				take = False
				if target >= nums[i]:
					take = dp[i - 1][j - nums[i]]
				dp[i][j] = take or nottake
		mini = 10 ** 8
		for i in range(Sum + 1):
			if dp[n - 1][i]:
				mini = min(mini, abs(i - (Sum - i)))
		return mini


class Solution:

	def minDifference(self, arr, n):
		total = sum(arr)
		dp = [True if i == 0 else False for i in range(total + 1)]
		if arr[0] <= total:
			dp[arr[0]] = True
		for i in range(1, n):
			curr = [True if i == 0 else False for i in range(total + 1)]
			for j in range(1, total + 1):
				not_selected = dp[j]
				selected = False
				if j >= arr[i]:
					selected = dp[j - arr[i]]
				curr[j] = selected or not_selected
			dp = curr
		min_diff = total
		for (idx, val) in enumerate(dp):
			if val:
				diff = abs(total - 2 * idx)
				if diff < min_diff:
					min_diff = diff
		return min_diff


class Solution:

	def minDifference(self, arr, n):
		sm = sum(arr)
		dp = [[True for i in range(sm + 1)] for j in range(n + 1)]
		for i in range(1, 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]
		mi = sm
		mid = len(dp[-1]) // 2 + 1
		for i in range(mid):
			if dp[-1][i]:
				mi = min(mi, abs(sm - 2 * i))
		return mi


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		dp = [[False for j 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, n + 1):
			for j in range(1, s + 1):
				dp[i][j] = dp[i - 1][j]
				if arr[i - 1] <= j:
					dp[i][j] |= dp[i - 1][j - arr[i - 1]]
		diff = float('inf')
		for j in range(s // 2 + 1):
			if dp[n][j]:
				diff = min(diff, s - 2 * j)
		return diff


class Solution:

	def minDifference(self, arr, n):
		n = len(arr)
		k = 0
		for i in range(n):
			k = k + arr[i]
		dp = [[False for i in range(k + 1)] for i in range(n)]
		for i in range(n):
			dp[i][0] = True
		if abs(arr[0]) <= k:
			dp[0][arr[0]] = True
		for ind in range(1, n):
			for target in range(1, k + 1):
				notTake = dp[ind - 1][target]
				Take = False
				if target >= arr[ind]:
					Take = dp[ind - 1][target - arr[ind]]
				dp[ind][target] = notTake or Take
		mini = 1000000000.0
		for i in range(k + 1):
			if dp[n - 1][i] == True:
				s1 = i
				s2 = k - i
				mini = min(mini, abs(s1 - s2))
		return mini


class Solution:

	def minDifference(self, arr, n):
		s = 0
		for ele in arr:
			s += ele
		S = int(s / 2)
		N = n
		dp = [[False] * (N + 1) for i in range(S + 1)]
		for i in range(N + 1):
			dp[0][i] = True
		for i in range(1, S + 1):
			for j in range(1, N + 1):
				if arr[j - 1] <= i:
					dp[i][j] = dp[i][j - 1] or dp[i - arr[j - 1]][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		for i in range(S, -1, -1):
			if dp[i][N] == True:
				return abs(s - 2 * i)


class Solution:

	def minDifference(self, arr, n):
		sum_val = 0
		for i in arr:
			sum_val += i
		res = [[False for i in range(sum_val + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			res[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, sum_val + 1):
				if arr[i - 1] > j:
					res[i][j] = res[i - 1][j]
				else:
					res[i][j] = res[i - 1][j] or res[i - 1][j - arr[i - 1]]
		diff = float('inf')
		for j in range(sum_val // 2, -1, -1):
			if res[n][j] == True:
				diff = sum_val - 2 * j
				break
		return diff


class Solution:

	def minDifference(self, arr, n):
		targetSum = sum(arr)
		mini = targetSum
		dp = [[False for i in range(targetSum + 1)] for j in range(len(arr) + 1)]
		for i in range(len(arr) + 1):
			dp[i][0] = True
		for i in range(1, len(arr) + 1):
			for j in range(1, targetSum + 1):
				dp[i][j] = dp[i - 1][j]
				if arr[i - 1] <= j:
					dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i - 1]]
				if dp[i][j]:
					remainigSum = targetSum - j
					mini = min(mini, abs(j - remainigSum))
		return mini


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		if n == 1:
			return s
		target = s // 2
		dp = [[False] * (n + 1) for _ in range(0, target + 1)]
		for i in range(0, n + 1):
			dp[0][i] = True
		ans = float('inf')
		for i in range(1, target + 1):
			for j in range(0, n):
				dp[i][j + 1] = dp[i][j]
				if i - arr[j] >= 0 and dp[i - arr[j]][j]:
					dp[i][j + 1] = True
			if dp[i][n]:
				ans = s - 2 * i
		return ans


class Solution:

	def minDifference(self, arr, n):
		target = sum(arr)
		dp = [[False for j in range(target + 1)] for i in range(n)]
		for i in range(n):
			dp[i][0] = True
		if arr[0] <= target:
			dp[0][arr[0]] = True
		for i in range(n):
			for j in range(target + 1):
				npick = dp[i - 1][j]
				pick = False
				if arr[i] <= j:
					pick = dp[i - 1][j - arr[i]]
				dp[i][j] = pick or npick
		import sys
		min_ = sys.maxsize
		for j in range(target + 1):
			if dp[n - 1][j]:
				s1 = j
				s2 = target - s1
				min_ = min(min_, abs(s1 - s2))
		return min_


class Solution:

	def minDifference(self, arr, n):
		sum = 0
		for i in arr:
			sum += i
		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
		mini = sum
		for i in range(sum // 2 + 1):
			if dp[n - 1][i] == True:
				mini = min(mini, abs(sum - i - i))
		return mini


class Solution:

	def minDifference(self, arr, n):

		def subset(arr, sm):
			n = len(arr)
			t = [[-1 for j in range(sm + 1)] for i in range(n + 1)]
			for j in range(sm + 1):
				t[0][j] = False
			for i in range(n + 1):
				t[i][0] = True
			for i in range(1, n + 1):
				for j in range(1, sm + 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]
			v = []
			for j in range(sm // 2 + 1):
				if t[n][j]:
					v.append(j)
			return v
		nums = subset(arr, sum(arr))
		mn = 1e+18
		for i in range(len(nums) - 1, -1, -1):
			mn = min(mn, sum(arr) - 2 * nums[i])
		return mn


class Solution:

	def minDifference(self, arr, n):
		totalSum = sum(arr)
		if n == 1:
			return arr[0]
		dp = [[-1 for i in range(totalSum + 1)] for j in range(n + 1)]

		def solve(ind, target):
			if target == 0:
				return True
			if ind == 0:
				return arr[0] == target
			if dp[ind][target] != -1:
				return dp[ind][target]
			take = False
			notTake = False
			if arr[ind] <= target:
				take = solve(ind - 1, target - arr[ind])
			notTake = solve(ind - 1, target)
			dp[ind][target] = take or notTake
			return dp[ind][target]
		for i in range(0, totalSum + 1):
			solve(n - 1, i)
		mine = float('inf')
		for i in range(totalSum + 1):
			if dp[n - 1][i]:
				diff = abs(i - (totalSum - i))
				mine = min(mine, diff)
		return mine % (10 ** 9 + 7)


class Solution:

	def minDifference(self, arr, n):
		k = sum(arr)
		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]]
		mini = int(1000000000.0)
		for i in range(k + 1):
			if dp[n - 1][i] == 1:
				diff = abs(i - (k - i))
				mini = min(mini, diff)
		return mini


class Solution:

	def minDifference(self, arr, n):
		if n == 1:
			return arr[0]
		s = sum(arr)
		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 j == 0:
					dp[i][j] = True
				elif i == 0:
					dp[i][j] = 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] or dp[i - 1][j - arr[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		m = int(10000000000.0)
		for i in range(1, n + 1):
			for j in range(1, s // 2 + 1):
				if dp[i][j] == True:
					m = min(m, s - j * 2)
		return m


class Solution:

	def minDifference(self, arr, n):
		sumTotal = 0
		for i in range(n):
			sumTotal += arr[i]
		memo = [[-1 for j in range(sumTotal + 1)] for i in range(n + 1)]

		def findMinRecMemoized(arr, i, sumCalculated, sumTotal, memo):
			if memo[i][sumCalculated] != -1:
				return memo[i][sumCalculated]
			if i == 0:
				memo[i][sumCalculated] = abs(sumTotal - sumCalculated - sumCalculated)
				return memo[i][sumCalculated]
			memo[i][sumCalculated] = min(findMinRecMemoized(arr, i - 1, sumCalculated + arr[i - 1], sumTotal, memo), findMinRecMemoized(arr, i - 1, sumCalculated, sumTotal, memo))
			return memo[i][sumCalculated]
		return findMinRecMemoized(arr, n, 0, sumTotal, memo)


class Solution:

	def minDifference(self, arr, n):
		sum = 0
		for i in range(n):
			sum += arr[i]
		dp = [[False 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:
					dp[i][j] = False
				if j == 0:
					dp[i][j] = True
		for i in range(1, n + 1):
			for j in range(1, sum + 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]
		v = []
		for i in range(sum // 2 + 1):
			if dp[n][i] == True:
				v.append(i)
		mn = float('inf')
		for it in v:
			mn = min(mn, sum - 2 * it)
		return mn


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		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:
				if i not in d:
					d.add(i)
			new = []
			if t in d:
				return 0
		ans = s
		for i in d:
			cur = 2 * abs(t - i)
			ans = min(ans, cur)
		return int(ans)


class Solution:

	def minDifference(self, arr, n):
		Sum = sum(arr)
		s1 = Sum // 2
		dp = [[False for i in range(s1 + 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, s1 + 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]]
		res = Sum
		for j in range(s1 + 1):
			if dp[n][j]:
				res = min(res, Sum - 2 * j)
		return res


class Solution:

	def minDifference(self, arr, n):
		sum_arr = sum(arr)
		dp = [[0] * (sum_arr + 1) for i in range(n + 1)]
		for i in range(sum_arr + 1):
			dp[0][i] = False
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, sum_arr + 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]
		for i in range((sum_arr + 1) // 2 + 1):
			if dp[n][i]:
				result = abs(sum_arr - 2 * i)
		return result


class Solution:

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

	def minDifference(self, arr, n):
		SUM = sum(arr)
		dp = [[-1 for _ in range(SUM)] for _ in range(n)]
		for i in range(SUM):
			self.solve(n - 1, arr, i, dp)
		ans = float('inf')
		for i in range(SUM):
			if dp[n - 1][i] == 1:
				ans = min(ans, abs(2 * i - SUM))
		return ans


class Solution:

	def minDifference(self, arr, n):
		summ = sum(arr)
		tab = [[False for i in range(summ + 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, summ + 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]]
		diff = 100000000000000000000000000000000
		for j in range(summ // 2, -1, -1):
			if tab[n][j] == True:
				diff = summ - 2 * j
				break
		return diff


class Solution:

	def minDifference(self, arr, n):
		total = sum(arr)
		dp = [[-1] * (total + 1) for i in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = 1
		for j in range(1, total + 1):
			dp[0][j] = 0
		for i in range(1, N + 1):
			for j in range(1, total + 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]
		mini = 10 ** 8
		for j in range(total + 1):
			if dp[n][j] == 1:
				s1 = j
				s2 = total - j
				mini = min(mini, abs(s2 - s1))
		return mini


class Solution:

	def minDifference(self, arr, n):
		a = arr
		target = sum(a)
		n = len(a)
		dp = [[False for j in range(target + 1)] for i 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, target + 1):
				if a[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - a[i - 1]]
		for i in range(sum(a) // 2, -1, -1):
			if dp[n][i] == True:
				return sum(a) - 2 * i


import math

class Solution:

	def minDifference(self, arr, n):
		stones = arr
		dp = {}
		s = sum(stones)
		target = math.ceil(s / 2)

		def solve(n, amt):
			if amt >= target or n == len(stones):
				return abs(s - amt - amt)
			if (n, amt) in dp:
				return dp[n, amt]
			dp[n, amt] = min(solve(n + 1, amt), solve(n + 1, amt + stones[n]))
			return dp[n, amt]
		return solve(0, 0)


class Solution:

	def minDifference(self, arr, n):
		target = sum(arr)
		dp = [[-1 for i in range(target + 1)] for j in range(n + 1)]
		return self.dfs(arr, n, target, dp)

	def dfs(self, arr, n, target, dp):
		if n == 0:
			return abs(sum(arr) - 2 * target)
		if dp[n][target] != -1:
			return dp[n][target]
		dp[n][target] = min(self.dfs(arr, n - 1, target, dp), self.dfs(arr, n - 1, target - arr[n - 1], dp))
		return dp[n][target]


import sys

class Solution:

	def minDifference(self, arr, n):
		total_sum = sum(arr)
		memo = [[False for j in range(total_sum // 2 + 1)] for i in range(n + 1)]
		for i in range(len(memo)):
			memo[i][0] = True
		for i in range(1, len(memo)):
			for j in range(1, len(memo[0])):
				if arr[i - 1] <= j:
					memo[i][j] = memo[i - 1][j - arr[i - 1]] or memo[i - 1][j]
				else:
					memo[i][j] = memo[i - 1][j]
		min_diff = float('inf')
		for i in range(len(memo[0]) - 1, -1, -1):
			if memo[-1][i]:
				min_diff = min(min_diff, abs(total_sum - 2 * i))
				return min_diff


class Solution:

	def minDifference(self, arr, n):
		sumCount = sum(arr)
		(lSum, rSum) = (sumCount, sumCount)
		dp = [[-1 for i in range(sumCount + 1)] for j in range(n + 1)]
		return self.dfs(arr, n, lSum, rSum, dp)

	def dfs(self, arr, n, lSum, rSum, dp):
		if n == 0:
			return abs(lSum - rSum)
		elif dp[n][lSum] != -1:
			return dp[n][lSum]
		dp[n][lSum] = min(self.dfs(arr, n - 1, lSum - arr[n - 1], rSum, dp), self.dfs(arr, n - 1, lSum, rSum - arr[n - 1], dp))
		return dp[n][lSum]


class Solution:

	def minDifference(self, arr, n):
		sumCount = sum(arr)
		dp = [[-1 for i in range(sumCount + 1)] for j in range(n + 1)]
		return self.dfs(arr, n, sumCount, 0, dp)

	def dfs(self, arr, n, sumL, sumR, dp):
		if n == 0:
			return abs(sumL - sumR)
		if dp[n][sumL] != -1:
			return dp[n][sumL]
		dp[n][sumL] = min(self.dfs(arr, n - 1, sumL - arr[n - 1], sumR + arr[n - 1], dp), self.dfs(arr, n - 1, sumL, sumR, dp))
		return dp[n][sumL]


import math
from functools import lru_cache

class Solution:

	def minDifference(self, nums, n):
		totalSum = sum(nums)

		@lru_cache(None)
		def dp(sum1, i):
			if i == -1:
				return abs(totalSum - 2 * sum1)
			ans = dp(sum1, i - 1)
			ans = min(ans, dp(sum1 + nums[i], i - 1))
			return ans
		return dp(0, n - 1)


class Solution:

	def minDifference(self, arr, n):
		high = sum(arr)
		temp = []
		dp = dict()
		self.subsetSum(arr, n, high // 2, 0, 0, temp, dp)
		res = float('inf')
		for t in temp:
			res = min(res, high - 2 * t)
		return res

	def subsetSum(self, arr, n, limit, index, total, temp, dp):
		if index == n:
			if total <= limit:
				temp.append(total)
			return
		if (index, total) in dp:
			return dp[index, total]
		if arr[index] > limit:
			dp[index, total] = self.subsetSum(arr, n, limit, index + 1, total, temp, dp)
		else:
			dp[index, total] = self.subsetSum(arr, n, limit, index + 1, total + arr[index], temp, dp)
			dp[index, total] = self.subsetSum(arr, n, limit, index + 1, total, temp, dp)


from itertools import product

class Solution:

	def minDifference(self, arr, n):
		sm = sum(arr)
		tab = [[False] * (sm + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			tab[i][0] = True
		for (i, j) in product(range(1, N + 1), range(1, sm + 1)):
			tab[i][j] = tab[i - 1][j] if arr[i - 1] > j else tab[i - 1][j] or tab[i - 1][j - arr[i - 1]]
		return next((sm - 2 * j for j in range(sm // 2, -1, -1) if tab[N][j]), float('inf'))


class Solution:

	def Divide_Subset(self, arr, sum_total, subset_sum, index, dp):
		if index == -1:
			return abs(sum_total - 2 * subset_sum)
		if dp[subset_sum][index] != -1:
			return dp[subset_sum][index]
		ans = min(self.Divide_Subset(arr, sum_total, subset_sum + arr[index], index - 1, dp), self.Divide_Subset(arr, sum_total, subset_sum, index - 1, dp))
		dp[subset_sum][index] = ans
		return ans

	def minDifference(self, arr, n):
		index = len(arr) - 1
		sum_total = sum(arr)
		dp = [[-1] * (index + 1) for i in range(sum_total)]
		return self.Divide_Subset(arr, sum_total, 0, index, dp)


class Solution:

	def SubSum(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] = False
		for i in range(N + 1):
			for j in range(sum + 1):
				if j == 0:
					t[i][j] = True
		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

	def minDifference(self, arr, n):
		Sum = sum(arr)
		t = self.SubSum(arr, Sum, n)
		res = t[-1]
		poss = []
		news = Sum // 2 + 1
		for i in range(len(res)):
			if i < news and res[i] == True:
				poss.append(i)
		mini = float('inf')
		for i in poss:
			if mini > Sum - 2 * i:
				mini = Sum - 2 * i
		return mini


class Solution:

	def minDifference(self, arr, n):
		S = 0
		for i in arr:
			S += i
		N = len(arr)
		t = [[False for i in range(S + 1)] for j in range(N + 1)]
		for i in range(N + 1):
			t[i][0] = True
		for i in range(1, N + 1):
			for j in range(1, S + 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]
		A = t[N]
		mn = 0
		for i in range(S // 2, -1, -1):
			if A[i]:
				mn = S - 2 * i
				break
		return mn


class Solution:

	def minDifference(self, arr, n):
		N = n
		su = sum(arr)
		dp = [[False] * (su + 1) for i in range(N)]
		for i in range(N):
			dp[i][0] = True
		if arr[0] <= su:
			dp[0][arr[0]] = True
		for i in range(1, N):
			for j in range(1, su + 1):
				dp[i][j] = dp[i - 1][j]
				if j - arr[i] >= 0:
					dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i]]
		minDiff = float('inf')
		for j in range(su + 1):
			isPoss = dp[n - 1][j]
			if isPoss:
				minDiff = min(minDiff, abs(j - (su - j)))
		return minDiff


class Solution:

	def minDifference(self, nums, n):
		if len(nums) == 1:
			return nums[0]
		minn = float('inf')
		total = sum(nums)
		dp = {}
		return self.findMin(nums, len(nums) - 1, total, total, minn, dp)

	def findMin(self, nums, idx, target, total, minn, dp):
		if idx == 0:
			if total != target:
				return min(minn, abs(total - target - target))
			return float('inf')
		if (idx, target) in dp:
			return dp[idx, target]
		pick = self.findMin(nums, idx - 1, target - nums[idx], total, minn, dp)
		notPick = self.findMin(nums, idx - 1, target, total, minn, dp)
		minn = min(pick, notPick)
		dp[idx, target] = minn
		return dp[idx, target]


class Solution:

	def minDifference(self, nums, n):
		Sum = sum(nums)
		n = len(nums)
		Mid = Sum // 2
		dp = [[False for _ in range(Mid + 1)] for _ 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, Mid + 1):
				if j - nums[i - 1] >= 0:
					dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		for i in range(Mid, -1, -1):
			if dp[-1][i] == True:
				return Sum - 2 * i
		return Sum


class Solution:

	def minDifference(self, arr, n):
		target = 0
		for el in arr:
			target += el
		dp = [[0 for i in range(target + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(n - 1, -1, -1):
			for j in range(target + 1):
				inc = 0
				if j - arr[i] >= 0:
					inc = dp[i + 1][j - arr[i]]
				exc = dp[i + 1][j]
				dp[i][j] = inc or exc
		ans = 999999999
		for i in range(target + 1):
			if dp[0][i] == 1:
				ans = min(ans, abs(target - i - i))
		return ans


def minimumSumPartition(n, arr):
	total = sum(arr)
	dp = [[0 for _ in range(total + 1)] for _ 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, total + 1):
			if j >= arr[i - 1] and dp[i - 1][j - arr[i - 1]] == 1:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i - 1][j]
	mini = 10 ** 10
	for j in range(total + 1):
		if dp[n][j] and mini > abs(j - (total - j)):
			mini = abs(j - (total - j))
	return mini

class Solution:

	def minDifference(self, arr, n):
		res = minimumSumPartition(n, arr)
		return res


class Solution:

	def minDifference(self, nums, n):
		dp = {}
		nums.sort()
		total = sum(nums)
		self.res = 99999999999
		done = set()

		def backtracking(i, p1):
			if (i, p1) in done:
				return
			p2 = total - p1
			self.res = min(self.res, p1 - p2)
			done.add((i, p1))
			if i >= n:
				return
			if p1 - nums[i] >= total - p1 + nums[i]:
				backtracking(i + 1, p1 - nums[i])
				backtracking(i + 1, p1)
			else:
				return
		backtracking(0, total)
		return self.res


class Solution:

	def minDifference(self, arr, n):
		s = sum(arr)
		dp = [[0 for i in range(s + 1)] for i in range(n + 1)]

		def subsetsum(arr, n, sum, dp):
			for i in range(n + 1):
				dp[i][0] = 1
			for i in range(1, n + 1):
				for j in range(1, sum + 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]
		subsetsum(arr, n, s, dp)
		min_diff = float('inf')
		for j in range(s // 2, -1, -1):
			if dp[n][j]:
				min_diff = s - 2 * j
				break
		return min_diff


class Solution:

	def minDifference(self, arr, n):
		total = sum(arr)
		sumArr = self.subsetSum(arr, total, n)
		index = len(sumArr) // 2
		low = float('inf')
		for i in range(index + 1):
			low = min(low, total - 2 * sumArr[i])
			if low < 0:
				low = -low
		return low

	def subsetSum(self, arr, total, n):
		subset = [[False for j in range(total + 1)] for i in range(n + 1)]
		for j in range(total + 1):
			subset[0][j] = False
		for i in range(n + 1):
			subset[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, total + 1):
				if arr[i - 1] > total:
					subset[i][j] = subset[i - 1][j]
				else:
					subset[i][j] = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]
		sumArr = []
		for j in range(total + 1):
			if subset[len(arr)][j] == True:
				sumArr.append(j)
		return sumArr