Partition Array Into Two Arrays to Minimize Sum Difference

The definition of the problem is an instruction: try every way to pick n of the 2n elements. Each n-subset fixes the first array, the remaining elements form the second, and the absolute difference follows immediately. This is correct by exhaustion, but the count of subsets explodes combinatorially.

from itertools import combinations


class Solution:
    def minimumDifference(self, nums: list[int]) -> int:
        n = len(nums) // 2
        total = sum(nums)
        best = float("inf")
        for chosen in combinations(range(2 * n), n):
            chosen_sum = sum(nums[i] for i in chosen)
            # first array sum = chosen_sum, second = total - chosen_sum
            best = min(best, abs(total - 2 * chosen_sum))
        return best

Why it is too slow: there are C(2n, n) subsets to visit, and each one costs O(n) to sum, so the total is O(C(2n, n) * n) — around 2.3 billion operations at n = 15. Enumeration is the right idea, but it must be done on two half-size piles, not the full array. Storage is just the combination being built, O(n).

Cut nums into a left half and a right half, each of length n. For each half, enumerate all 2^n subsets and record the signed sum of the subset: elements given to the first array count +, the rest count -. Group those signed sums by how many elements were chosen, so f[i] holds every signed sum obtainable by choosing exactly i elements from the left, and g[j] does the same on the right.

The reason prefixes f and g fit together is the count constraint. If the left gives i elements to the first array, the right must give exactly n - i, so the total difference for that pair is a + b with a in f[i] and b in g[n - i]. The signed sums already encode both arrays, so no separate subtraction is needed. For each a, the best possible b is the value closest to -a; sort each g group once and find it with a binary search. Checking the insertion point and the element before it covers both neighbors.

from bisect import bisect_left


class Solution:
    def minimumDifference(self, nums: list[int]) -> int:
        n = len(nums) // 2
        left, right = nums[:n], nums[n:]
        # f[i]: signed sums of the left half choosing exactly i elements
        # g[j]: signed sums of the right half choosing exactly j elements
        f = [set() for _ in range(n + 1)]
        g = [set() for _ in range(n + 1)]

        for mask in range(1 << n):
            s = cnt = 0
            for j in range(n):
                if mask >> j & 1:
                    s += left[j]
                    cnt += 1
                else:
                    s -= left[j]
            f[cnt].add(s)

        for mask in range(1 << n):
            s = cnt = 0
            for j in range(n):
                if mask >> j & 1:
                    s += right[j]
                    cnt += 1
                else:
                    s -= right[j]
            g[cnt].add(s)

        best = float("inf")
        for i in range(n + 1):
            right_sums = sorted(g[n - i])
            for a in f[i]:
                target = -a
                p = bisect_left(right_sums, target)
                if p < len(right_sums):
                    best = min(best, abs(a + right_sums[p]))
                if p > 0:
                    best = min(best, abs(a + right_sums[p - 1]))
        return best

Watch the two grouped tables fill one bitmask at a time, then watch the pairing readout binary-search the right table for the complement of each left value.

Why it is fast enough: each half enumerates 2^n masks and scans n bits per mask, so building f and g is O(n * 2^n). Sorting all the g groups together is also O(n * 2^n) because each group is at most 2^n long. The pairing loop performs one O(log 2^n) = O(n) binary search per left sum, again O(n * 2^n). At n = 15 that is roughly half a million operations. Space is O(2^n) for the two tables, which hold at most 2^n distinct signed sums each.