Split Array Into Two Arrays to Minimize Sum Difference

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size() / 2;
        long long total = accumulate(nums.begin(), nums.end(), 0LL);
        vector<vector<long long>> L(n + 1), R(n + 1);
        for (int mask = 0; mask < (1 << n); ++mask) {
            long long sl = 0, sr = 0;
            int cnt = __builtin_popcount(mask);
            for (int i = 0; i < n; ++i) if (mask >> i & 1) {
                sl += nums[i];
                sr += nums[n + i];
            }
            L[cnt].push_back(sl);
            R[cnt].push_back(sr);
        }
        for (auto& v : R) sort(v.begin(), v.end());

        long long best = LLONG_MAX;
        for (int k = 0; k <= n; ++k) {
            const auto& cand = R[n - k];
            if (cand.empty()) continue;
            for (long long sl : L[k]) {
                long long need = total - 2 * sl;        // want 2 * sr ≈ need
                long long needHalf = need / 2;
                auto it = lower_bound(cand.begin(), cand.end(), needHalf);
                for (auto p : {it, (it == cand.begin() ? cand.end() : prev(it))}) {
                    if (p == cand.end()) continue;
                    long long sumA = sl + *p;
                    best = min(best, llabs(total - 2 * sumA));
                }
            }
        }
        return (int)best;
    }
};

import (
    "math"
    "sort"
)

func minimumDifference(nums []int) int {
    n := len(nums) / 2
    var total int64
    for _, v := range nums {
        total += int64(v)
    }
    L := make([][]int64, n+1)
    R := make([][]int64, n+1)
    for mask := 0; mask < (1 << n); mask++ {
        var sl, sr int64
        cnt := 0
        for i := 0; i < n; i++ {
            if mask>>i&1 == 1 {
                sl += int64(nums[i])
                sr += int64(nums[n+i])
                cnt++
            }
        }
        L[cnt] = append(L[cnt], sl)
        R[cnt] = append(R[cnt], sr)
    }
    for _, v := range R {
        sort.Slice(v, func(a, b int) bool { return v[a] < v[b] })
    }
    best := int64(math.MaxInt64)
    abs := func(x int64) int64 {
        if x < 0 {
            return -x
        }
        return x
    }
    for k := 0; k <= n; k++ {
        cand := R[n-k]
        if len(cand) == 0 {
            continue
        }
        for _, sl := range L[k] {
            need := total - 2*sl // want 2 * sr ≈ need
            needHalf := need / 2
            idx := sort.Search(len(cand), func(i int) bool { return cand[i] >= needHalf })
            candidates := []int{}
            if idx < len(cand) {
                candidates = append(candidates, idx)
            }
            if idx > 0 {
                candidates = append(candidates, idx-1)
            }
            for _, p := range candidates {
                sumA := sl + cand[p]
                d := abs(total - 2*sumA)
                if d < best {
                    best = d
                }
            }
        }
    }
    return int(best)
}

import bisect
from typing import List

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 2
        total = sum(nums)
        L: List[List[int]] = [[] for _ in range(n + 1)]
        R: List[List[int]] = [[] for _ in range(n + 1)]
        for mask in range(1 << n):
            sl = sr = 0
            cnt = 0
            for i in range(n):
                if (mask >> i) & 1:
                    sl += nums[i]
                    sr += nums[n + i]
                    cnt += 1
            L[cnt].append(sl)
            R[cnt].append(sr)
        for v in R:
            v.sort()

        best = float('inf')
        for k in range(n + 1):
            cand = R[n - k]
            if not cand:
                continue
            for sl in L[k]:
                need = total - 2 * sl  # want 2 * sr ~ need
                need_half = need // 2
                idx = bisect.bisect_left(cand, need_half)
                for p in (idx, idx - 1):
                    if 0 <= p < len(cand):
                        sum_a = sl + cand[p]
                        d = abs(total - 2 * sum_a)
                        if d < best:
                            best = d
        return int(best)

function minimumDifference(nums) {
    const n = nums.length / 2;
    let total = 0;
    for (const v of nums) total += v;
    const L = Array.from({ length: n + 1 }, () => []);
    const R = Array.from({ length: n + 1 }, () => []);
    for (let mask = 0; mask < (1 << n); mask++) {
        let sl = 0, sr = 0, cnt = 0;
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                sl += nums[i];
                sr += nums[n + i];
                cnt++;
            }
        }
        L[cnt].push(sl);
        R[cnt].push(sr);
    }
    for (const v of R) v.sort((a, b) => a - b);

    const lowerBound = (arr, target) => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };

    let best = Infinity;
    for (let k = 0; k <= n; k++) {
        const cand = R[n - k];
        if (!cand.length) continue;
        for (const sl of L[k]) {
            const need = total - 2 * sl;          // want 2 * sr ≈ need
            const needHalf = Math.floor(need / 2);
            const idx = lowerBound(cand, needHalf);
            for (const p of [idx, idx - 1]) {
                if (p >= 0 && p < cand.length) {
                    const sumA = sl + cand[p];
                    const d = Math.abs(total - 2 * sumA);
                    if (d < best) best = d;
                }
            }
        }
    }
    return best;
}

class Solution {
    private int lowerBound(long[] arr, long target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    public int minimumDifference(int[] nums) {
        int n = nums.length / 2;
        long total = 0;
        for (int v : nums) total += v;
        List<List<Long>> L = new ArrayList<>();
        List<List<Long>> R = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            L.add(new ArrayList<>());
            R.add(new ArrayList<>());
        }
        for (int mask = 0; mask < (1 << n); mask++) {
            long sl = 0, sr = 0;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (((mask >> i) & 1) == 1) {
                    sl += nums[i];
                    sr += nums[n + i];
                    cnt++;
                }
            }
            L.get(cnt).add(sl);
            R.get(cnt).add(sr);
        }
        long[][] Rsorted = new long[n + 1][];
        for (int i = 0; i <= n; i++) {
            long[] arr = new long[R.get(i).size()];
            for (int j = 0; j < arr.length; j++) arr[j] = R.get(i).get(j);
            Arrays.sort(arr);
            Rsorted[i] = arr;
        }
        long best = Long.MAX_VALUE;
        for (int k = 0; k <= n; k++) {
            long[] cand = Rsorted[n - k];
            if (cand.length == 0) continue;
            for (long sl : L.get(k)) {
                long need = total - 2 * sl; // want 2 * sr ~ need
                long needHalf = need / 2;
                int idx = lowerBound(cand, needHalf);
                int[] ps = {idx, idx - 1};
                for (int p : ps) {
                    if (p >= 0 && p < cand.length) {
                        long sumA = sl + cand[p];
                        long d = Math.abs(total - 2 * sumA);
                        if (d < best) best = d;
                    }
                }
            }
        }
        return (int) best;
    }
}

function minimumDifference(nums: number[]): number {
    const n = nums.length / 2;
    let total = 0;
    for (const v of nums) total += v;
    const L: number[][] = Array.from({ length: n + 1 }, () => []);
    const R: number[][] = Array.from({ length: n + 1 }, () => []);
    for (let mask = 0; mask < (1 << n); mask++) {
        let sl = 0, sr = 0, cnt = 0;
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                sl += nums[i];
                sr += nums[n + i];
                cnt++;
            }
        }
        L[cnt].push(sl);
        R[cnt].push(sr);
    }
    for (const v of R) v.sort((a, b) => a - b);

    const lowerBound = (arr: number[], target: number): number => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };

    let best = Infinity;
    for (let k = 0; k <= n; k++) {
        const cand = R[n - k];
        if (!cand.length) continue;
        for (const sl of L[k]) {
            const need = total - 2 * sl;          // want 2 * sr ~ need
            const needHalf = Math.floor(need / 2);
            const idx = lowerBound(cand, needHalf);
            for (const p of [idx, idx - 1]) {
                if (p >= 0 && p < cand.length) {
                    const sumA = sl + cand[p];
                    const d = Math.abs(total - 2 * sumA);
                    if (d < best) best = d;
                }
            }
        }
    }
    return best;
}