We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition Array Into Two Arrays to Minimize Sum Difference

Difficulty: Hard

Problem Description

You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. To partition nums, put each element of nums into one of the two arrays.

Return the minimum possible absolute difference.

Key Insights

  • The problem can be viewed as a variation of the subset sum problem where we need to split the array into two equal halves.
  • The total sum of the array can be calculated, and our goal is to find a subset whose sum is as close as possible to half of the total sum.
  • Since n is at most 15, we can use a bitmask approach to explore all possible combinations of the numbers.

Space and Time Complexity

Time Complexity: O(2^n * n)
Space Complexity: O(n)

Solution

We will utilize a bitmask to generate all possible combinations of the elements in the array. For each combination that represents one of the two partitions, we will calculate the sum of that partition and derive the sum of the other partition from the total sum. We will then compute the absolute difference and keep track of the minimum difference found.

  1. Calculate the total sum of the array.
  2. Iterate through all possible subsets (using bitmasking).
  3. For each subset, compute its sum and derive the sum of the other subset.
  4. Calculate the absolute difference and update the minimum difference accordingly.

Code Solutions

def minimumDifference(nums):
    n = len(nums) // 2
    total_sum = sum(nums)
    half_sum = total_sum // 2
    sums = []

    # Generate all possible sums for half of the array
    for mask in range(1 << n):
        subset_sum = 0
        count = 0
        for i in range(n):
            if mask & (1 << i):
                subset_sum += nums[i]
                count += 1
        if count == n:
            sums.append(subset_sum)

    sums.sort()
    min_diff = float('inf')

    for sum1 in sums:
        sum2 = total_sum - sum1
        min_diff = min(min_diff, abs(sum1 - sum2))

    return min_diff
← Back to All Questions