Solution: Split Array Into Two Arrays to Minimize Sum Difference

Statement

You are given an integer array, nums, consisting of $2 * n$ elements.

Your task is to divide the array into two subarrays of length $n$, such that each element in nums belongs to exactly one of the two subarrays, and the absolute difference between their sum is minimized.

Return the minimum possible absolute difference between the sum of the two subarrays.

Constraints:

• 1 $\leq$ $n$ $\leq$ 15

• nums.length $== 2 * n$

• $-10^{7}$ $\leq$ nums[i] $\leq$ $10^{7}$

Solution

The essence of this solution lies in minimizing the absolute difference between the sums of two equal-sized subarrays by leveraging the binary search pattern combined with the meet-in-the-middle strategy. Instead of evaluating all possible partitions, which would be computationally infeasible due to the exponential number of subsets, the array is split into two halves. All possible subset sums are computed for each half, along with the number of elements used to form them. The key insight is that for each subset generated from the left half, we determine how many elements are needed from the right half (so the total subset size equals n), and then use binary search to efficiently find the best-matching subset from the right half whose sum brings the total closest to half the total array sum.

This process is both precise and optimized because:

• Right-half subsets are pregrouped by their size, making it possible to only consider valid combinations (those with a total of n elements).

• Each group of subset sums is sorted, allowing binary search to be used for fast and accurate retrieval of the closest matching subset sum.

• Only 2ⁿ subsets are generated per half (not 2^(2n)), drastically reducing time complexity.

As a result, this method efficiently finds the best partition without exhaustively testing all combinations, achieving a powerful reduction in both time and space.

Now, let’s look at the solution steps below:

1. Compute half_len, total_sum, and target_sum as the key parameters to guide the partitioning logic.

2. Split nums into left_half and right_half.

3. Generate all subset sums for left_half and store them as (count, subset_sum) pairs in left_subsets.

4. Generate all subset sums for right_half and store them in right_subsets.

5. Group right_subsets into a dictionary right_sum_dict by count, and sort each group for binary search.

6. For each subset in left_subsets, compute how many elements must come from the right (right_count = half_len - count).

7. Use binary search on right_sum_dict[right_count] to find the closest sum to target_sum - left_sum.

8. Track the smallest difference encountered and update min_diff accordingly.

9. Return the final result as min_diff * 2 + total_sum % 2.

Let’s look at the following illustration to get a better understanding of the solution: