LeetCode Solutions Blog

Partition Array Into Two Arrays to Minimize Sum Difference

Number: 2162

Difficulty: Hard

Paid? No

Problem Description

Given an integer array nums of length 2*n, partition the array into two arrays each of length n such that the absolute difference between their sums is minimized. You achieve this by choosing exactly n elements for one array, with the remaining forming the other array. Return the minimum possible absolute difference between the sums of the two arrays.

Key Insights

The problem is equivalent to choosing n elements from 2*n such that the sum of chosen elements is as close as possible to half of the total sum.
Use the meet-in-the-middle strategy by splitting the array into two halves; each half has at most 15 elements.
For each half, enumerate all possible subset sums along with the count of elements chosen.
Combine subset sums from the first and second halves with complementary counts (j and n-j) and use binary search to quickly find the best pairing that minimizes the absolute difference.
The final answer is given by abs(total - 2*(chosenSubsetSum)).

Space and Time Complexity

Time Complexity: O(2^(n) * n) due to enumerating subset sums in each half (with n up to 15, 2^(15) is feasible) and then combining results with binary search. Space Complexity: O(2^(n)) for storing subset sums for each half.

Solution

We use a meet-in-the-middle approach:

Divide the array into two halves.
For each half, generate all possible subset sums along with the number of elements selected. This can be stored in a dictionary keyed by the count of selected numbers.
The goal is to form a subset of exactly n elements. For every possible selection count j from the first half, pair it with selections of n-j from the second half.
For each pair, compute the total subset sum. The optimal subset sum should be as close as possible to half the total sum. Thus, the minimum absolute difference is given by abs(total - 2*(subset sum)).
To efficiently find the best sum candidate from the second half for a given value from the first half, sort the sums from the second half for each selection count and use binary search.
Return the minimal absolute difference found.

Code Solutions

# Python solution using meet-in-the-middle
from collections import defaultdict
import bisect

def minimumDifference(nums):
    n = len(nums) // 2
    total = sum(nums)
    
    # Function to generate all subset sums for a list of numbers.
    # Returns a dictionary mapping count of numbers chosen => list of subset sums.
    def generate_subsets(arr):
        subsets = defaultdict(list)
        subsets[0].append(0)
        # For each number in the array, update possible sums with increased count.
        for num in arr:
            current = list(subsets.items())
            for cnt, sums in current:
                for s in sums:
                    subsets[cnt + 1].append(s + num)
        return subsets

    # Split the array into two halves.
    first_half = nums[:n]
    second_half = nums[n:]
    
    # Generate possible subset sums for both halves.
    left = generate_subsets(first_half)
    right = generate_subsets(second_half)
    
    # Sort sums in right half for each possible count to allow binary search.
    for cnt in right:
        right[cnt].sort()
    
    best_diff = float('inf')
    
    # For each possible count j chosen from the first half, we need to choose (n-j) from the second.
    for j in range(n+1):
        left_sums = left[j]
        right_sums = right[n - j]
        # For each sum from the first half possibilities.
        for sum_left in left_sums:
            # The ideal target for the total chosen sum is roughly half of the total.
            target = total / 2 - sum_left
            # binary search in the sorted list of right_sums.
            idx = bisect.bisect_left(right_sums, target)
            # Check candidate at idx.
            if idx < len(right_sums):
                current = sum_left + right_sums[idx]
                best_diff = min(best_diff, abs(total - 2 * current))
            # Also check candidate at idx-1 if it exists.
            if idx > 0:
                current = sum_left + right_sums[idx - 1]
                best_diff = min(best_diff, abs(total - 2 * current))
    return best_diff

# Example usage:
# nums = [3,9,7,3]
# print(minimumDifference(nums))  # Output should be 2