Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The input contains 2 * n integers. Every number must go into one of two arrays, and each array must contain exactly n numbers. The goal is to make the absolute difference between the two array sums as small as possible.

Choosing one array completely determines the other. If all numbers sum to T and the chosen n numbers sum to S, the two array sums are S and T - S, so their difference is

$$ \left|S - (T - S)\right| = \left|T - 2S\right|. $$

The problem is therefore equivalent to choosing exactly n numbers whose sum is as close as possible to half of T. The exact-size requirement is crucial: a subset with the perfect sum is useless if it contains the wrong number of elements.

Deriving the optimal solution

A direct search considers every subset of 2 * n elements, which is roughly $2^{2n}$. The constraint is small enough for an exponential algorithm, but not for that much exponential work. Meet in the middle cuts the exponent in half.

Split nums into a left half and a right half, each containing n values. Enumerate every subset of each half. Instead of putting all subset sums together, group them by how many elements produced the sum:

  • left_sums[k] contains sums made by choosing exactly k left-half values.
  • right_sums[k] contains sums made by choosing exactly k right-half values.

If a candidate takes k elements from the left, it must take exactly n - k from the right. That pairing of groups enforces the required total of n selected elements automatically.

Now fix a left subset sum L. A matching right sum R should make L + R as close as possible to T / 2. Equivalently, R should be close to T / 2 - L. Sort the matching right-sum group and use binary search to find where that target belongs. Only the value at the insertion point and its predecessor can be closest; every other value lies even farther away in the sorted order.

For example, with [3, 9, 7, 3], the halves are [3, 9] and [7, 3]. Choosing one value from each half gives left sums [3, 9] and right sums [7, 3]. Pairing left sum 3 with right sum 7 selects [3, 7], whose sum is 10. The total is 22, so the difference is |22 - 2 * 10| = 2.

This search is complete because every valid choice of n values has some left-side count k, and its right-side count must be n - k. Its two subset sums appear in exactly those complementary groups. The algorithm examines every left sum and the best possible right partner for it, so it cannot miss the optimal partition.

There are $2^n$ subset sums in each half. Generating them takes $O(2^n)$ time, sorting the right-side groups takes $O(n2^n)$ time, and the binary searches take $O(n2^n)$ time. The total complexity is $O(n2^n)$ time and $O(2^n)$ space, where the original array length is 2 * n.

Python solution

from collections.abc import Sequence


class Solution:
    """Find the most balanced equal-cardinality partition of an integer array."""

    def minimumDifference(self, nums: list[int]) -> int:
        """Return the minimum difference between two equal-size partition sums.

        The implementation does not modify ``nums``. LeetCode guarantees a
        positive even input length; validation keeps the method safe if reused.
        """
        self._validate_input(nums)

        half_size = len(nums) // 2
        total_sum = sum(nums)
        left_sums_by_count = self._group_subset_sums(nums[:half_size])
        right_sums_by_count = self._group_subset_sums(nums[half_size:])

        # Only the right groups need sorting because they are the search side.
        for subset_sums in right_sums_by_count:
            subset_sums.sort()

        # The first half itself is a valid size-n choice and gives a safe bound.
        best_difference = abs(total_sum - 2 * sum(nums[:half_size]))

        for left_count, left_sums in enumerate(left_sums_by_count):
            right_count = half_size - left_count
            sorted_right_sums = right_sums_by_count[right_count]

            for left_sum in left_sums:
                # We want right_sum closest to total_sum / 2 - left_sum.
                # Doubling both sides avoids floating-point arithmetic.
                target_twice = total_sum - 2 * left_sum
                insertion_index = self._lower_bound_for_doubled_sum(
                    sorted_right_sums,
                    target_twice,
                )

                # The closest sorted value is the insertion point or predecessor.
                for right_index in (insertion_index - 1, insertion_index):
                    if 0 <= right_index < len(sorted_right_sums):
                        selected_sum = left_sum + sorted_right_sums[right_index]
                        difference = abs(total_sum - 2 * selected_sum)
                        best_difference = min(best_difference, difference)

                if best_difference == 0:
                    return 0

        return best_difference

    @staticmethod
    def _group_subset_sums(values: Sequence[int]) -> list[list[int]]:
        """Return every subset sum, grouped by the subset's cardinality."""
        sums_by_count: list[list[int]] = [
            [] for _ in range(len(values) + 1)
        ]

        def explore(index: int, chosen_count: int, subset_sum: int) -> None:
            if index == len(values):
                sums_by_count[chosen_count].append(subset_sum)
                return

            # Leave the current value out of the subset.
            explore(index + 1, chosen_count, subset_sum)

            # Put the current value into the subset.
            explore(
                index + 1,
                chosen_count + 1,
                subset_sum + values[index],
            )

        explore(index=0, chosen_count=0, subset_sum=0)
        return sums_by_count

    @staticmethod
    def _lower_bound_for_doubled_sum(
        sorted_sums: Sequence[int],
        target_twice: int,
    ) -> int:
        """Find the first index whose value doubled reaches the target."""
        low = 0
        high = len(sorted_sums)

        while low < high:
            middle = low + (high - low) // 2
            if 2 * sorted_sums[middle] < target_twice:
                low = middle + 1
            else:
                high = middle

        return low

    @staticmethod
    def _validate_input(values: Sequence[int]) -> None:
        """Reject inputs that cannot form two nonempty equal-size arrays."""
        if len(values) < 2 or len(values) % 2 != 0:
            raise ValueError("nums must contain a positive, even number of values")

Interview follow-ups

Can the matching phase avoid a binary search for every left sum?

Yes. Sort both left_sums[k] and right_sums[n - k]. Start one pointer at the smallest left sum and another at the largest right sum. If twice their combined sum is below T, advance the left pointer; otherwise, move the right pointer down. Record the best difference at every step.

The sum changes monotonically in the needed direction, so skipping the discarded pointer position cannot hide a closer pair. Across all complementary count groups, the matching scan becomes $O(2^n)$ rather than $O(n2^n)$. Sorting all groups still costs $O(n2^n)$ in the worst case, so the overall asymptotic bound is unchanged, but the two-pointer version can reduce binary-search overhead.

How would the solution return the two partitions, not just the difference?

Store (subset_sum, bitmask) records instead of sums alone. Whenever a left record and right record improve the answer, remember both masks. After the search, use the masks to collect the selected indices from each half; every unselected index belongs to the other partition.

The proof is unchanged because the masks only preserve the identity of the values that produced each sum. Time remains $O(n2^n)$. Space stays $O(2^n)$ asymptotically, although each stored record is larger and reconstruction needs $O(n)$ additional time.

What if the two arrays do not need equal lengths?

Then the subset cardinality no longer matters. Generate all subset sums for each half without grouping them by count, sort the right sums, and for every left sum search for the right sum closest to T / 2 - left_sum.

Every subset of the full input is still a union of one left subset and one right subset, so the same completeness argument applies. If the original input length is N, this version takes $O(N2^{N/2})$ time and $O(2^{N/2})$ space. It is simpler, but it would be incorrect for the original problem because it could choose the wrong number of elements.

When is count-aware dynamic programming a better alternative?

If all values are nonnegative and their total sum T is modest, maintain a bitset or Boolean table for each chosen count. State (c, s) records whether some c elements can produce sum s. Process each number once, update counts backward, and finally inspect reachable sums for count n near T / 2.

The state transition is the standard include-or-skip subset argument, so every reachable exact-size subset is represented. The cost is pseudo-polynomial: roughly $O(NnT)$ with a Boolean table, or much faster in practice with bitset shifts, and $O(nT)$ space. It can beat meet in the middle when T is small, but large values or negative values make the required sum range too wide unless an offset is introduced.

How would the algorithm count all optimal partitions?

First compute the minimum difference. Then store frequencies of equal subset sums within every cardinality group. During a second matching pass, find every right sum that combines with a left sum to achieve that difference and add the product of their frequencies. This counts all labeled choices for the first partition without expanding duplicate sums into separate search records.

The complement of every chosen n-element subset produces the same unordered partition with the two sides swapped. Therefore, if the interviewer considers swapping the two output arrays to be the same partition, divide the final labeled count by two. The time remains governed by subset generation and sorting, while frequency maps may substantially reduce work when many subset sums repeat.

Can this approach scale to much larger arrays?

Not in the general case. Equal-cardinality number partitioning is still a combinatorial problem, and meet in the middle only reduces the exponent from the full input size to half of it. Larger arbitrary integers quickly make both $2^{N/2}$ time and memory impractical.

The right alternative depends on what extra structure the interviewer allows. Small sum ranges favor count-aware dynamic programming; approximate answers favor greedy balancing or approximation schemes; repeated values may allow frequency compression; and special distributions may support branch-and-bound pruning. Without such structure, there is no general polynomial-time replacement that preserves an exact answer.