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: interview

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]


#Re-use of my  dynamic programing approach for spliting the workload part I
#Given a set S of n non-negative integers:
# 1) make a partition of S with exactly two subsets A,B of S, such that the absolute
#    difference of the elements of each set is minimized

#To solve this problem, all we need to do is use the general subset sum program, but
# set the target sum to S/2 where S is the sum of all of the elements in the list
from collections import Counter     #for differencing lists with (possible) duplicates


#Build the dynamic programing table:  Column are the sums, and rows are the subsets
#   DP[i][j] == True if and only if there exists a subset of {a[0],...,a[i-1]} such
#               that the a[0]+...+a[i-1]==j 
# Row i is the subset {a[0],...,a[i-1]}
# Col j is a number (representing a sum)
#The function additionally builds a 'parent' table that is used to determine
# the optimal path (which will allow us to get the elements in the subsets)
def getdDPTable( numList, sizeList, targetSum):

    numRows = sizeList + 1       #to account for empty set, we need +1
    numCols  = targetSum + 1     #to account for zero, we need +1

    #initialize both tables
    dp     = [ [False for _ in range(numCols)] for _ in range(numRows) ]
    parent = [ [ []   for _ in range(numCols)] for _ in range(numRows) ]

    #The sum of 0 can be achieved by selecting no elements from each possible subsets
    #  That is, it is true we can always acheive the sum of 0 from any possible subset
    for r in range(numRows):
        dp[r][0] = True
    
    #increasing in rows, and from left to right wrt columns, we build the rest
    # of the DP table row i corresponds to the set {a_0,...,a_i}, column j
    # corresponds to the target sum j.  If d[i][j] is true, that means there
    # exists a subset of  {a_0,...,a_i} whose elemenst sum to j 
    for r in range(1, numRows):
        for c in range(1, numCols):
            if c < numList[r-1]:            #on row r, current column is less than numList[r-1]
                dp[r][c] = dp[r-1][c]       #see row above for whether there exists a subeset that sums to j
                parent[r][c].append(tuple( [r-1, c] ))   #we store where we got the answer
            else:                           #we must perform a backtrack on the previous row
                alreadyBuilt = dp[r-1][c]                           #look at row above
                isInOriginalNumList   = dp[r-1][c - numList[r-1]]   #look at backtrack
                dp[r][c] = alreadyBuilt or isInOriginalNumList

                #we store the parent that is true
                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
#---end function


#Here, using the parent table that was built (when building the dynamic programming table)
# we extract the subset elements that form the optimal target sum
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     
#---end function



#In the scenario we can not find the best case scenario of a set with
#  the target sum of (sum of entire set)/2 (as then the difference would be 0)
# We must find the next best number, which is determined by the largest column
# in the DP table (as this corresponds to the largest possible sum that can be made) 
def getBestNum(dp, numList, targetSum, numRows):

    for j in range(targetSum,-1,-1):
        if dp[numRows-1][j]==True:      #found the largest sum we can make
            break

    return j
#---end function


#The main driver to solve the minimum partion problem
# Exmaple: [0, 20, 54, 99, 84, 99] has a minimum partion of ([99, 54, 20], [0, 99, 84]) 
#          that has a difference of 10
#First we try to partition the number list into equal valued sets (whose elements sum to
#  the same number).  If that works, we found that the min diff is 0, so make the two  
#  subsets and return them.  If we have a list of numbers where we can't partition them
#  into equal values, we have to find the largest possible sum we can make.  Then, simply
#  find the subset that makes that largest number, and we are done
def splitlist(numList):
    
    sizeList = len(numList)

    #First see if we can get a subset that sums to sum(numList)//2 (then diff would be zero)
    targetSum = sum(numList)//2 
    dp, parent, numRows, numCols = getdDPTable(numList, sizeList, targetSum)
    
    foundSubset = dp[numRows-1][targetSum]

    bestDiff = 0
    if foundSubset:     #We found a subset whose elements sum to the target sum(numList)//2
        subsetA = getSubset(parent, numRows, targetSum)
    else:
        #We could not get the best case senario, so we need to find the largest possible subset
        # sum tha we can make given the provided list of numbers (see e.x. [0, 20, 54, 99, 84, 99])
        newTargetSum = getBestNum(dp, numList, targetSum, numRows)
        dp, parent, numRows, numCols = getdDPTable(numList, sizeList, newTargetSum)
        subsetA = getSubset(parent, numRows, newTargetSum)

    #partition the provided list of numbers into two subsets A and B
    c1 = Counter(numList)
    c2 = Counter(subsetA)
    diff = c1-c2
    subsetB = list(diff.elements())
    
    return subsetA, subsetB
#---end function


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]

# we get the least difference between the two lists if the sums are equal, i.e. each lists sum is half the the sum of the
#entire list. If we can't achieve that, we get as close to that target as possible. In other words, the solution uses the knapsack
#problem, in particular subset sum. We have a bag that has a capacity sum(lst)/2 which we are trying to fill as much as possible
#using elements from lst

def splitlist(lst):
  
    if not lst: return ([],[])
    target = sum(lst)//2
    
    #dp array for knapsack problem
    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
    #get the values of the items in the first segment (the items which we used to get our max capacity in dp array)
    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]
    
    #remove all items from list which belong to seg 1
    seg2 = [a for a in lst]
    for a in seg1: seg2.remove(a)
    
    return (seg1,seg2)


def splitlist(x):
    """
    a, b = splitlist(x) finds a partition a, b of x minimizing |sum(a)-sum(b)|
    """
    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