LeetCode 2035 - Partition Array Into Two Arrays to Minimize Sum Difference

The problem gives an array nums containing exactly 2 n integers. We must divide these integers into two separate groups, each containing exactly n elements. After forming the two groups, we compute the sum of each group and measure the absolute difference between those sums.

leetcodehardarraytwo-pointersbinary-searchdynamic-programmingbit-manipulationsortingordered-setbitmask

LeetCode Problem 2035

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Dynamic Programming, Bit Manipulation, Sorting, Ordered Set, Bitmask

Solution

Problem Understanding

The problem gives an array nums containing exactly 2 * n integers. We must divide these integers into two separate groups, each containing exactly n elements. After forming the two groups, we compute the sum of each group and measure the absolute difference between those sums.

Our goal is to minimize that absolute difference.

More formally, if the two groups are:

  • Group A with sum sumA
  • Group B with sum sumB

then we want to minimize:

$$|sumA - sumB|$$

An important detail is that both groups must contain exactly n elements. This constraint prevents us from simply balancing sums greedily.

The input size is small enough to suggest exponential techniques, but large enough that brute force over all partitions is impossible.

The constraints are:

  • 1 <= n <= 15
  • nums.length == 2 * n

This means the maximum array length is only 30, but the number of possible ways to choose 15 elements from 30 is:

$$\binom{30}{15} \approx 155,117,520$$

Trying every partition directly would be far too slow.

The values in the array may also be negative, which means techniques based on only positive sums, such as classic subset sum DP indexed by sum, become difficult because sums can range across large negative and positive values.

Several edge cases are important:

  • Arrays containing negative values
  • Arrays where the optimal difference is zero
  • Arrays with only two elements
  • Arrays where all values are identical
  • Arrays where one side must intentionally include large positive and negative values together to balance the total

The problem guarantees that a valid partition always exists because the array size is always even.

Approaches

Brute Force

The brute force solution tries every possible way to choose n elements from the 2n elements.

For each selection:

  1. Compute the sum of the chosen subset.
  2. Compute the sum of the remaining elements.
  3. Calculate the absolute difference.
  4. Track the minimum.

This guarantees correctness because every valid partition is examined.

However, the number of subsets is enormous.

The number of ways to choose n elements from 2n is:

$$\binom{2n}{n}$$

For n = 15, this is over 155 million possibilities.

Even if each evaluation were very fast, iterating through all combinations would exceed time limits.

Key Insight

The crucial observation is that n <= 15, which makes a meet-in-the-middle strategy feasible.

Instead of processing all 30 elements together, we split the array into two halves:

  • Left half of size n
  • Right half of size n

We then enumerate subset sums independently for each half.

For every subset, we store:

  • How many elements were chosen
  • The resulting sum

Later, we combine subsets from the left and right halves so that the total number of chosen elements equals n.

This reduces the complexity dramatically because:

  • Each half has at most 2^15 = 32768 subsets
  • Enumerating all subsets becomes manageable

The remaining challenge is efficiently finding complementary sums that minimize the final difference. Sorting and binary search solve this efficiently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(\binom{2n}{n})$ $O(1)$ Tries every possible partition
Optimal Meet-in-the-Middle $O(n \cdot 2^n)$ $O(2^n)$ Splits the problem into two smaller subset enumeration problems

Algorithm Walkthrough

Step 1: Compute the Total Sum

First compute:

totalSum = sum(nums)

If one partition has sum chosenSum, then the other partition has sum:

totalSum - chosenSum

The resulting difference becomes:

$$|chosenSum - (totalSum - chosenSum)|$$

which simplifies to:

$$|2 \cdot chosenSum - totalSum|$$

So the problem becomes finding a subset of exactly n elements whose sum is as close as possible to:

$$\frac{totalSum}{2}$$

Step 2: Split the Array into Two Halves

Divide the array into:

left = nums[:n]
right = nums[n:]

Each half contains exactly n elements.

Step 3: Enumerate All Subset Sums for Each Half

For every subset mask from 0 to 2^n - 1:

  1. Count how many elements are selected.
  2. Compute the subset sum.

Store the sums grouped by subset size.

Example structure:

leftSums[k] = all subset sums using k elements
rightSums[k] = all subset sums using k elements

This organization is important because the final partition must contain exactly n elements total.

If we choose k elements from the left half, then we must choose n-k elements from the right half.

Step 4: Sort the Right Half Sums

For every subset size:

rightSums[k].sort()

Sorting allows binary search later.

Step 5: Try Every Left Subset

For each left subset sum:

  • Suppose it uses k elements
  • Then we need n-k elements from the right half

Let:

leftSum = current left subset sum

The total chosen sum becomes:

leftSum + rightSum

We want this value as close as possible to:

$$\frac{totalSum}{2}$$

Rearranging:

target = totalSum / 2 - leftSum

Now binary search inside rightSums[n-k] to find the closest value to target.

Step 6: Update the Minimum Difference

For each candidate:

chosen = leftSum + rightSum
difference = abs(totalSum - 2 * chosen)

Update the global minimum.

Why it works

The algorithm examines every valid partition indirectly.

Every subset of the original array can be represented as:

  • Some subset from the left half
  • Some subset from the right half

By grouping sums according to subset size, we guarantee that the final combined subset contains exactly n elements.

Binary search ensures we efficiently find the complementary subset sum that minimizes the final difference.

Because every valid partition is considered and the minimum difference is tracked globally, the algorithm always returns the optimal answer.

Python Solution

from typing import List
from collections import defaultdict
import bisect

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 2
        
        left = nums[:n]
        right = nums[n:]
        
        left_sums = defaultdict(list)
        right_sums = defaultdict(list)
        
        # Generate all subset sums for left half
        for mask in range(1 << n):
            count = 0
            subset_sum = 0
            
            for i in range(n):
                if mask & (1 << i):
                    count += 1
                    subset_sum += left[i]
            
            left_sums[count].append(subset_sum)
        
        # Generate all subset sums for right half
        for mask in range(1 << n):
            count = 0
            subset_sum = 0
            
            for i in range(n):
                if mask & (1 << i):
                    count += 1
                    subset_sum += right[i]
            
            right_sums[count].append(subset_sum)
        
        # Sort right sums for binary search
        for count in right_sums:
            right_sums[count].sort()
        
        total_sum = sum(nums)
        answer = float("inf")
        
        # Combine left and right subsets
        for left_count in left_sums:
            right_count = n - left_count
            
            right_list = right_sums[right_count]
            
            for left_sum in left_sums[left_count]:
                target = total_sum / 2 - left_sum
                
                idx = bisect.bisect_left(right_list, target)
                
                # Check candidate at idx
                if idx < len(right_list):
                    chosen_sum = left_sum + right_list[idx]
                    diff = abs(total_sum - 2 * chosen_sum)
                    answer = min(answer, diff)
                
                # Check candidate before idx
                if idx > 0:
                    chosen_sum = left_sum + right_list[idx - 1]
                    diff = abs(total_sum - 2 * chosen_sum)
                    answer = min(answer, diff)
        
        return answer

The implementation follows the meet-in-the-middle strategy directly.

The array is split into two halves. For each half, every possible subset is enumerated using bitmasks. The subset size and subset sum are computed simultaneously.

The sums are grouped by subset size because the final chosen subset must contain exactly n elements total.

After generating the subset sums, the right half lists are sorted. This enables binary search for the best complementary subset sum.

For every left subset sum, the algorithm computes the ideal target value from the right side that would bring the combined sum as close as possible to half of the total array sum.

Binary search identifies the nearest candidates efficiently. Since the exact closest value may lie either at the insertion position or immediately before it, both positions are checked.

The minimum absolute difference is updated throughout the process.

Go Solution

package main

import (
	"math"
	"sort"
)

func minimumDifference(nums []int) int {
	n := len(nums) / 2

	left := nums[:n]
	right := nums[n:]

	leftSums := make([][]int, n+1)
	rightSums := make([][]int, n+1)

	// Generate subset sums for left half
	for mask := 0; mask < (1 << n); mask++ {
		count := 0
		sum := 0

		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 {
				count++
				sum += left[i]
			}
		}

		leftSums[count] = append(leftSums[count], sum)
	}

	// Generate subset sums for right half
	for mask := 0; mask < (1 << n); mask++ {
		count := 0
		sum := 0

		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 {
				count++
				sum += right[i]
			}
		}

		rightSums[count] = append(rightSums[count], sum)
	}

	// Sort right side sums
	for i := 0; i <= n; i++ {
		sort.Ints(rightSums[i])
	}

	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}

	answer := math.MaxInt32

	for leftCount := 0; leftCount <= n; leftCount++ {
		rightCount := n - leftCount

		rightList := rightSums[rightCount]

		for _, leftSum := range leftSums[leftCount] {
			target := float64(totalSum)/2.0 - float64(leftSum)

			idx := sort.Search(len(rightList), func(i int) bool {
				return float64(rightList[i]) >= target
			})

			// Check idx
			if idx < len(rightList) {
				chosenSum := leftSum + rightList[idx]
				diff := abs(totalSum - 2*chosenSum)

				if diff < answer {
					answer = diff
				}
			}

			// Check idx - 1
			if idx > 0 {
				chosenSum := leftSum + rightList[idx-1]
				diff := abs(totalSum - 2*chosenSum)

				if diff < answer {
					answer = diff
				}
			}
		}
	}

	return answer
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation closely mirrors the Python version.

Instead of dictionaries, Go uses slices of slices:

[][]int

where index k stores all subset sums using exactly k elements.

Binary search is implemented using sort.Search, which returns the first index satisfying the condition.

Go does not provide a built in absolute value function for integers, so a custom abs helper is included.

All calculations safely fit inside 32 bit integers because the maximum possible sum is:

$$30 \times 10^7 = 3 \times 10^8$$

which remains within Go's integer range.

Worked Examples

Example 1

nums = [3,9,7,3]

Here:

n = 2
left = [3,9]
right = [7,3]
totalSum = 22

Left subset sums

Mask Elements Count Sum
00 [] 0 0
01 [3] 1 3
10 [9] 1 9
11 [3,9] 2 12

So:

leftSums[0] = [0]
leftSums[1] = [3, 9]
leftSums[2] = [12]

Right subset sums

Mask Elements Count Sum
00 [] 0 0
01 [7] 1 7
10 [3] 1 3
11 [7,3] 2 10

After sorting:

rightSums[1] = [3, 7]

Combining subsets

Suppose:

leftSum = 3
leftCount = 1

Then:

rightCount = 1
target = 11 - 3 = 8

Binary search in [3,7] gives closest value 7.

So:

chosenSum = 3 + 7 = 10
difference = |22 - 20| = 2

Minimum answer becomes 2.

Example 2

nums = [-36,36]

We must split into:

[-36] and [36]

Sums:

-36 and 36

Difference:

72

The algorithm evaluates both possibilities and returns 72.

Example 3

nums = [2,-1,0,4,-2,-9]

n = 3
totalSum = -6
target half = -3

One optimal partition is:

[2,4,-9] => -3
[-1,0,-2] => -3

Difference:

0

The binary search step eventually finds complementary subset sums producing exactly half of the total sum.

Complexity Analysis

Measure Complexity Explanation
Time $O(n \cdot 2^n)$ Enumerating all subsets and performing binary searches
Space $O(2^n)$ Storage for subset sums

The dominant work comes from enumerating all subsets of each half.

Each half contains n elements, so there are:

$$2^n$$

subsets.

For every subset we spend O(n) time computing the sum using bit checks.

Sorting all subset sum lists collectively costs:

$$O(2^n \log 2^n)$$

which is still manageable for n <= 15.

The memory usage comes from storing all subset sums, which also totals O(2^n) values.

Test Cases

sol = Solution()

assert sol.minimumDifference([3,9,7,3]) == 2
# Basic example from problem statement

assert sol.minimumDifference([-36,36]) == 72
# Smallest possible array size

assert sol.minimumDifference([2,-1,0,4,-2,-9]) == 0
# Perfect partition exists

assert sol.minimumDifference([1,2]) == 1
# Two positive numbers

assert sol.minimumDifference([0,0,0,0]) == 0
# All zeros

assert sol.minimumDifference([5,5,5,5]) == 0
# Identical values

assert sol.minimumDifference([1,1,1,9]) == 8
# Large imbalance

assert sol.minimumDifference([-5,-5,10,10]) == 0
# Negative and positive balancing

assert sol.minimumDifference([10000000,-10000000,7,-7]) == 0
# Large magnitude values

assert sol.minimumDifference([8,-3,5,-2,1,-6]) == 1
# Mixed values with near-optimal partition
Test Why
[3,9,7,3] Validates standard example
[-36,36] Smallest valid input size
[2,-1,0,4,-2,-9] Confirms exact zero partition
[1,2] Simple positive case
[0,0,0,0] All sums identical
[5,5,5,5] Repeated numbers
[1,1,1,9] Strong imbalance
[-5,-5,10,10] Positive and negative cancellation
[10000000,-10000000,7,-7] Large magnitude numbers
[8,-3,5,-2,1,-6] General mixed-value stress case

Edge Cases

Arrays with Negative Numbers

Negative numbers make traditional subset sum dynamic programming difficult because the sum range can become very large and include negative indices.

For example:

[-5, -2, 7, 10]

A naive DP indexed by sum would require offset handling and potentially huge memory.

The meet-in-the-middle approach avoids this entirely because it stores actual subset sums directly rather than indexing by them.

Perfectly Balanced Partitions

Sometimes the optimal answer is exactly zero.

Example:

[2,-1,0,4,-2,-9]

Both partitions can sum to -3.

The implementation correctly handles this because it searches for sums closest to totalSum / 2. If an exact match exists, binary search finds it and the answer becomes zero.

Minimum Input Size

When n = 1, the array contains only two elements.

Example:

[-36, 36]

The algorithm still works correctly because each half contains exactly one element, and the subset enumeration naturally handles subsets of size 0 and 1.

No special case handling is required.

Large Magnitude Values

The values can be as large as:

10^7

and there are up to 30 numbers.

The implementation avoids overflow issues because the maximum absolute total sum is:

$$30 \times 10^7 = 3 \times 10^8$$

which safely fits inside standard integer ranges in both Python and Go.