1
class Solution:
2
    def minimumDifference(self, nums: List[int]) -> int:
3
        n = len(nums) // 2
4
        left, right = nums[:n], nums[n:]
5
        lsum, rsum = sum(left), sum(right)
6

7
        ans = inf
8
        for i in range(n + 1):
9
            vals = sorted(2 * sum(combo) - lsum for combo in combinations(left, i))
10
            for combo in combinations(right, n - i):
11
                diff = 2 * sum(combo) - rsum
12
                k = bisect_left(vals, -diff)
13
                if k:
14
                    ans = min(ans, abs(vals[k - 1] + diff))
15
                if k < len(vals):
16
                    ans = min(ans, abs(vals[k] + diff))
17
        return ans