package main

import (
    "fmt"
    "math"
    "sort"
)

func main() {
    ret := minimumDifference([]int{3, 9, 7, 3})
    fmt.Println(ret)
}

func minimumDifference(arr []int) int {
    size := len(arr)
    half := size >> 1
    //HashMap<Integer, TreeSet<Integer>> lmap = new HashMap<>();
    lmap := make(map[int]map[int]struct{})
    process(arr, 0, half, 0, 0, lmap)
    //HashMap<Integer, TreeSet<Integer>> rmap = new HashMap<>();
    rmap := make(map[int]map[int]struct{})
    process(arr, half, size, 0, 0, rmap)
    sum := 0
    for _, num := range arr {
        sum += num
    }
    ans := math.MaxInt64
    for leftNum, _ := range lmap {
        for leftSum, _ := range lmap[leftNum] {
            rr := rmap[half-leftNum]
            //模拟treeset
            rarr := make([]int, 0)
            for r, _ := range rr {
                rarr = append(rarr, r)
            }
            sort.Ints(rarr)
            ri := NearestIndex2(rarr, (sum>>1)-leftSum)
            rightSum := 0
            if ri != -1 {
                rightSum = rarr[ri]
                pickSum := leftSum + rightSum
                restSum := sum - pickSum
                //ans = Math.min(ans, restSum - pickSum);
                if ans > restSum-pickSum {
                    ans = restSum - pickSum
                }
            }
        }
    }
    return ans
}

// arr -> 8   0 1 2 3      4 5 6 7
// process(arr, 0, 4)  [0,4)
// process(arr, 4, 8)  [4,8)
// arr[index....end-1]这个范围上，去做选择
// pick挑了几个数！
// sum挑的这些数，累加和是多少！
// map记录结果
// HashMap<Integer, TreeSet<Integer>> map
// key -> 挑了几个数，比如挑了3个数，但是形成累加和可能多个！
// value -> 有序表，都记下来！
// 整个过程，纯暴力！2^15 -> 3万多，纯暴力跑完，依然很快！
func process(arr []int, index int, end int, pick int, sum int, map0 map[int]map[int]struct{}) {
    if index == end {
        if _, ok := map0[pick]; !ok {
            map0[pick] = make(map[int]struct{})
        }
        map0[pick][sum] = struct{}{}
    } else {
        process(arr, index+1, end, pick, sum, map0)
        process(arr, index+1, end, pick+1, sum+arr[index], map0)
    }
}

// 在arr上，找满足<=value的最右位置
func NearestIndex2(arr []int, v int) int {
    L := 0
    R := len(arr) - 1
    index := -1 // 记录最右的对号
    for L <= R {
        mid := L + (R-L)>>1
        if arr[mid] <= v {
            index = mid
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    return index
}