# minimal difference splitting

Write a function that splits an integer list into two parts such that the difference of the sum of the two parts is the smallest among all possible splits.

``` \$ cat sl.rkt
#lang racket

(define (diff a b)
(abs (- a b)))

(define (split-list l)
(let ((sum (apply + l)))
(let loop ((left '()) (right l) (min-diff (abs sum)) (min-left '())
(min-right l) (left-sum 0) (right-sum sum))
(if (null? right)
(cons (reverse min-left) min-right)
(let*
((x (car right))
(lsum (+ left-sum x))
(rsum (- right-sum x))
(df (diff lsum rsum))
(l (cons x left))
(r (cdr right)))

(if (< df min-diff)
(loop l r df l r lsum rsum)
(loop l r min-diff min-left min-right lsum rsum)))))))

(require rackunit)

(check-equal? (split-list '()) '(()))
(check-equal? (split-list '(1 1)) '((1) 1))
(check-equal? (split-list '(2 7 3 1 4)) '((2 7) 3 1 4))
(check-equal? (split-list '(1 2 4 7 3)) '((1 2 4) 7 3))
(check-equal? (split-list '(-5 5)) '(() -5 5))

(define (check-min-diff-split lst)
(let*
((split (split-list lst))
(l-split (car split))
(r-split (cdr split))
(min-diff (diff (apply + l-split) (apply + r-split))))

(let loop ((right lst) (left-sum 0) (right-sum (apply + lst)))
(if (< (diff left-sum right-sum) min-diff)
(raise-user-error 'check-min-diff-split
"split difference isn't a minimum\n  ~a + ~a = ~a\n  ~a + ~a = ~a"
l-split r-split min-diff
(take lst (- (length lst) (length right))) right
(diff left-sum right-sum))
(unless (null? right)
(let
((x (car right)))
(loop (cdr right) (+ left-sum x) (- right-sum x))))))))

(define (test lst)
(for-each check-min-diff-split (permutations lst)))

(test '(1 1))
(test '(2 7 3 1 4))
(test '(-5 5))
(test '(0 1 2 3 4 5 6 7 8))

\$ mzscheme sl.rkt

\$
```