This is the second part of a two-part challenge. See [part I](https://www.codewars.com/kata/587387d169b6fddc16000002) if you haven't done so already.
The problem is the same, only with longer lists and larger values.

Imagine you have a number of jobs to execute. Your workers are not permanently connected to your network, so you have to distribute all your jobs in the beginning. Luckily, you know exactly how long each job is going to take. 

Let 
```
x = [2,3,4,6,8,2]
```
be the amount of time each of your jobs is going to take.

Your task is to write a function ```splitlist(x)```, that will return two lists ```a``` and ```b```, such that ```abs(sum(a)-sum(b))``` is minimised.

One possible solution to this example would be 
```
a=[2, 4, 6]
b=[3, 8, 2]
```
with  ```abs(sum(a)-sum(b)) == 1```.

The order of the elements is not tested, just make sure that you minimise ```abs(sum(a)-sum(b))``` and that ```sorted(a+b)==sorted(x)```.

You may assume that ```len(x)<=40``` and ```0<=x[i]<=1000```.

Difficulty: MEDIUM

Starter code:
def splitlist(lst):
	

Solutions:
def splitlist(l):
	half = sum(l) // 2
	sums = [(0, [])]
	for (i, n) in enumerate(l):
		sums = sums + [(m + n, a + [i]) for (m, a) in sums if m + n <= half]
		if max((s[0] for s in sums)) == half:
			break
	sums.sort(key=lambda v: abs(v[0] - half))
	indices = sums[0][1]
	return ([n for (i, n) in enumerate(l) if i in indices], [n for (i, n) in enumerate(l) if i not in indices])


from collections import Counter

def getdDPTable(numList, sizeList, targetSum):
	numRows = sizeList + 1
	numCols = targetSum + 1
	dp = [[False for _ in range(numCols)] for _ in range(numRows)]
	parent = [[[] for _ in range(numCols)] for _ in range(numRows)]
	for r in range(numRows):
		dp[r][0] = True
	for r in range(1, numRows):
		for c in range(1, numCols):
			if c < numList[r - 1]:
				dp[r][c] = dp[r - 1][c]
				parent[r][c].append(tuple([r - 1, c]))
			else:
				alreadyBuilt = dp[r - 1][c]
				isInOriginalNumList = dp[r - 1][c - numList[r - 1]]
				dp[r][c] = alreadyBuilt or isInOriginalNumList
				if alreadyBuilt:
					parent[r][c].append(tuple([r - 1, c]))
				if isInOriginalNumList:
					parent[r][c].append(tuple([r - 1, c - numList[r - 1]]))
	return (dp, parent, numRows, numCols)

def getSubset(parent, numRows, targetSum):
	subset = []
	child = [tuple([numRows - 1, targetSum])]
	(cRow, cCol) = (child[0][0], child[0][1])
	father = parent[numRows - 1][targetSum]
	while father:
		fRow = father[0][0]
		fCol = father[0][1]
		diff = cCol - fCol
		if diff != 0:
			subset.append(diff)
		cRow = fRow
		cCol = fCol
		father = parent[fRow][fCol]
	return subset

def getBestNum(dp, numList, targetSum, numRows):
	for j in range(targetSum, -1, -1):
		if dp[numRows - 1][j] == True:
			break
	return j

def splitlist(numList):
	sizeList = len(numList)
	targetSum = sum(numList) // 2
	(dp, parent, numRows, numCols) = getdDPTable(numList, sizeList, targetSum)
	foundSubset = dp[numRows - 1][targetSum]
	bestDiff = 0
	if foundSubset:
		subsetA = getSubset(parent, numRows, targetSum)
	else:
		newTargetSum = getBestNum(dp, numList, targetSum, numRows)
		(dp, parent, numRows, numCols) = getdDPTable(numList, sizeList, newTargetSum)
		subsetA = getSubset(parent, numRows, newTargetSum)
	c1 = Counter(numList)
	c2 = Counter(subsetA)
	diff = c1 - c2
	subsetB = list(diff.elements())
	return (subsetA, subsetB)


def splitlist(lst):
	if not lst:
		return ([], [])
	(half, n) = (sum(lst) >> 1, len(lst))
	lst = sorted(lst, reverse=1)
	DP = [[0] * (half + 1) for i in range(n + 1)]
	for (i, v) in enumerate(lst):
		for j in range(1, 1 + half):
			DP[i][j] = max(v + DP[i - 1][j - v], DP[i - 1][j]) if v <= j else DP[i - 1][j]
	(acc, j) = (DP[-2][-1], half)
	(a, b) = ([], [])
	for i in reversed(range(n)):
		v = lst[i]
		if acc != DP[i - 1][j]:
			a.append(v)
			acc -= v
			j -= v
		else:
			b.append(v)
	return (a, b)


def splitlist(l, i=0, sa=0, sb=0, sl=None, mem=None, first=False):
	if mem is None:
		(first, mem, sl) = (True, {}, sum(l))
	if i == len(l):
		return ([], []) if first else (abs(sa - sb), [])
	found = mem.get((i, sa))
	da = db = sl
	if not found and sa < sl / 2:
		(da, ma) = splitlist(l, i + 1, sa + l[i], sb, sl, mem)
		ma = [True] + ma
	if not found and da > 0 and (sb < sl / 2):
		(db, mb) = splitlist(l, i + 1, sa, sb + l[i], sl, mem)
		mb = [False] + mb
	if not found:
		found = mem.setdefault((i, sa), (da, ma) if da <= db else (db, mb))
	if not first:
		return found
	(a, b) = ([], [])
	for (v, m) in zip(l, found[1]):
		(a if m else b).append(v)
	return (a, b)


jcash = {}

def splitlist(lst):

	def splitl(i, w):
		g = jcash.get((i, w))
		if g:
			return g
		if i == len(lst):
			return []
		wi = lst[i]
		a1 = splitl(i + 1, w)
		if wi > w:
			jcash[i, w] = a1.copy()
			return a1
		a2 = splitl(i + 1, w - wi)
		if sum(a1) < sum(a2) + wi:
			a2.append(wi)
			jcash[i, w] = a2.copy()
			return a2
		else:
			jcash[i, w] = a1.copy()
			return a1
	jcash.clear()
	lst.sort()
	lst.reverse()
	a = splitl(0, sum(lst) // 2)
	b = lst.copy()
	for i in a:
		b.remove(i)
	return (a, b)


def splitlist(lst):
	if not lst:
		return ([], [])
	lst = sorted(lst, reverse=True)
	optimum = sum(lst) // 2
	if optimum <= lst[0]:
		return ([lst[0]], lst[1:])
	dp = [None] * (optimum + 1)
	dp[0] = []
	for item in lst:
		for pos in reversed(range(optimum - item + 1)):
			if dp[pos] is not None and dp[pos + item] is None:
				dp[pos + item] = dp[pos] + [item]
	best = next(reversed([option for option in dp if option is not None]))
	for item in best:
		lst.remove(item)
	return (best, lst)


def splitlist(lst):
	dicto = {}

	def spliteer(lst, sum1=0, sum2=0, ls1=[], ls2=[], i=0):
		key = f'{sum1}{i}'
		if key in dicto:
			return dicto[key]
		if i >= len(lst):
			return (abs(sum1 - sum2), [ls1, ls2])
		else:
			min1 = spliteer(lst, sum1 + lst[i], sum2, ls1 + [lst[i]], ls2, i + 1)
			min2 = spliteer(lst, sum1, sum2 + lst[i], ls1, ls2 + [lst[i]], i + 1)
			dicto[key] = min(min1, min2, key=lambda x: x[0])
		return dicto[key]
	return spliteer(lst)[1]


from copy import deepcopy
from random import shuffle

def splitlist(a):
	if a == []:
		return ([], [])
	elif len(a) == 1:
		return (a, [])
	b = deepcopy(a)
	s = sum(a)
	minimum = ((a,), s)
	for i in range(10000):
		shuffle(b)
		s2 = 0
		for (j, el) in enumerate(b):
			if s2 <= s / 2 and s2 + el > s / 2:
				break
			else:
				s2 += el
		if abs(sum(b[:j]) - sum(b[j:])) < minimum[1]:
			minimum = ((b[:j], b[j:]), abs(sum(b[:j]) - sum(b[j:])))
	return minimum[0]


def splitlist(lst):
	if not lst:
		return ([], [])
	target = sum(lst) // 2
	dp = [[0 for _ in range(target + 1)] for _ in range(len(lst) + 1)]
	for i in range(1, len(lst) + 1):
		for j in range(target + 1):
			if j >= lst[i - 1]:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - lst[i - 1]] + lst[i - 1])
			else:
				dp[i][j] = dp[i - 1][j]
	seg1 = []
	w = target
	for i in range(len(lst), -1, -1):
		if dp[i][w] - dp[i - 1][w - lst[i - 1]] == lst[i - 1]:
			seg1.append(lst[i - 1])
			w -= lst[i - 1]
	seg2 = [a for a in lst]
	for a in seg1:
		seg2.remove(a)
	return (seg1, seg2)


def splitlist(x):
	max_total = sum(x) // 2
	sumset = [{0}]
	for xi in x:
		sumset.append({t + xi for t in sumset[-1] if t + xi <= max_total} | sumset[-1])
	(a, b) = ([], [])
	total = max(sumset[-1])
	for (i, xi) in reversed(list(enumerate(x))):
		if total - xi in sumset[i]:
			a.append(xi)
			total -= xi
		else:
			b.append(xi)
	return (a, b)