Given a set of n integers, divide the set in two subsets, S1 and S2, of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. The task is to print that two subset S1 and S2. Elements in S1 and S2 should be present in same format as given in input.
Note: 
	If n is even, then sizes of two subsets must be strictly n/2 
	if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.
	n is strictly greater than 1.
	Minimum Diff = abs(s1-s2), where s1>s2.
Example 1:
Input: 
arr[] = {3, 4, 5, -3, 100, 
         1, 89, 54, 23, 20}
Output: 
148 148
Explanation:  Both output subsets 
are of size 5 and sum of elements in 
both subsets is same (148 and 148).
So the minimum difference will be 0.
Example 2:
Input: 
arr[] = {13, -17, 6, 48, -44, -14}
Output:
-10 2
Explanation: The sums of elements in 
two subsets are -10 and 2 respectively.
So the minimum difference will be (2-(-10))
=12.
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 array which incudes sum of each sub-arrays.
 
Expected Time Complexity: O(2^N)
Expected Space Complexity: O(2*N)
 
Constraints:
2 <= N <= 20
-10000 <= arr[i] <= 10000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





from typing import List





class Solution:

    def minDifference(self, n : int, arr : List[int]) -> List[List[int]]:

        # code here

        



Solutions:
from typing import List
from itertools import combinations

class Solution:

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		total = sum(arr)
		s1 = s2 = 0
		min_diff = float('inf')
		for subset in combinations(arr, n // 2):
			sum1 = sum(subset)
			sum2 = total - sum1
			if sum1 > sum2:
				(sum1, sum2) = (sum2, sum1)
			diff = abs(sum2 - sum1)
			if diff < min_diff:
				min_diff = diff
				(s1, s2) = (sum1, sum2)
		return [[s1], [s2]]

def Helper(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position):
	if curr_position == n:
		return
	if int(n / 2) - no_of_selected_elements > n - curr_position:
		return
	Helper(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
	no_of_selected_elements += 1
	curr_sum = curr_sum + arr[curr_position]
	curr_elements[curr_position] = True
	if no_of_selected_elements == int(n / 2):
		if abs(int(Sum / 2) - curr_sum) < min_diff[0]:
			min_diff[0] = abs(int(Sum / 2) - curr_sum)
			for i in range(n):
				soln[i] = curr_elements[i]
	else:
		Helper(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
	curr_elements[curr_position] = False


from typing import List
from itertools import combinations

class Solution:

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		total = sum(arr)
		s1 = s2 = 0
		min_diff = float('inf')
		for subset in combinations(arr, n // 2):
			sum1 = sum(subset)
			sum2 = total - sum1
			if sum1 > sum2:
				(sum1, sum2) = (sum2, sum1)
			diff = abs(sum2 - sum1)
			if diff < min_diff:
				min_diff = diff
				(s1, s2) = (sum1, sum2)
		return [[s1], [s2]]


from typing import List
from typing import List

class Solution:

	def __init__(self):
		self.ans = [[10 ** 10], [-10 ** 10]]

	def fill(self, i, n, a, b, arr):
		if i < 0:
			temp = abs(sum(a) - sum(b))
			if (n % 2 == 0 and len(a) == n // 2 or (n % 2 == 1 and (len(a) == n // 2 or len(b) == n // 2))) and temp < abs(sum(self.ans[0]) - sum(self.ans[1])):
				self.ans = [[sum(a)], [sum(b)]]
			return temp
		(c1, c2) = (0, 0)
		a.append(arr[i])
		c1 = self.fill(i - 1, n, a, b, arr)
		a.pop()
		b.append(arr[i])
		c2 = self.fill(i - 1, n, a, b, arr)
		b.pop()
		if c1 < c2:
			return c1
		else:
			return c2

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		(a, b) = ([], [])
		self.fill(n - 1, n, a, b, arr)
		self.ans = [min(self.ans), max(self.ans)]
		return self.ans


from typing import List
from typing import List
from collections import deque

class Solution:

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		Q = deque([[0, 0, 0, 0, 0]])
		n = len(arr)
		(a1, a2) = (float('-inf'), float('inf'))
		while Q:
			(s1, l1, s2, l2, i) = Q.popleft()
			if l1 > (n + 1) // 2 or l2 > (n + 1) // 2:
				continue
			if i == n:
				if max(s1, s2) - min(s1, s2) < a2 - a1:
					a2 = max(s1, s2)
					a1 = min(s1, s2)
				continue
			Q.append([s1 + arr[i], l1 + 1, s2, l2, i + 1])
			Q.append([s1, l1, s2 + arr[i], l2 + 1, i + 1])
		return ([a1], [a2])


from typing import List
from typing import List

class Solution:

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		global ans1
		global ans2
		global mini
		ans1 = [0]
		ans2 = [0]
		mini = [1000000000000.0]

		def rec(sumi1, sumi2, n, ind, p, q):
			global ans1
			global ans2
			global mini
			if n == ind:
				if abs(p - q) <= 1:
					if mini[0] > abs(sumi1 - sumi2):
						mini[0] = abs(sumi1 - sumi2)
						ans1[0] = sumi1
						ans2[0] = sumi2
				return
			else:
				t = arr[ind]
				rec(sumi1 + t, sumi2, n, ind + 1, p + 1, q)
				rec(sumi1, sumi2 + t, n, ind + 1, p, q + 1)
		rec(0, 0, n, 0, 0, 0)
		a = ans1[0]
		b = ans2[0]
		return [[min(a, b)], [max(a, b)]]


from typing import List
from typing import List

class Solution:

	def minDifference(self, n: int, arr: List[int]) -> List[List[int]]:
		curr_elements = [None] * n
		soln = [None] * n
		min_diff = [999999999999]
		Sum = 0
		for i in range(n):
			Sum += arr[i]
			curr_elements[i] = soln[i] = False
		TOWUtil(arr, n, curr_elements, 0, soln, min_diff, Sum, 0, 0)
		ans = []
		ans1 = []
		for i in range(n):
			if soln[i] == True:
				ans.append(arr[i])
			else:
				ans1.append(arr[i])
		return [ans, ans1]

def TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position):
	if curr_position == n:
		return
	if int(n / 2) - no_of_selected_elements > n - curr_position:
		return
	TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
	no_of_selected_elements += 1
	curr_sum = curr_sum + arr[curr_position]
	curr_elements[curr_position] = True
	if no_of_selected_elements == int(n / 2):
		if abs(int(Sum / 2) - curr_sum) < min_diff[0]:
			min_diff[0] = abs(int(Sum / 2) - curr_sum)
			for i in range(n):
				soln[i] = curr_elements[i]
	else:
		TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
	curr_elements[curr_position] = False