2035. Partition Array Into Two Arrays to Minimize Sum Difference
Asked at Salesforce
Difficulty
Hard
Time
O(2^(n/2) * n)
Space
O(2^(n/2))
Pattern
Array
Companies
1
Problem
You are given an integer array nums whose length is 2 * n. Split all of its elements into two groups of exactly n elements each. Every element must go into one of the two groups, and no element can be used twice.
Let S1 and S2 be the sums of the two groups. Return the smallest possible value of |S1 - S2| over all valid splits.
The order of elements does not matter, and the groups are not labeled — swapping the two groups gives the same difference. Because n can be up to 15, there are up to C(30, 15) splits, so trying every split one by one is too slow. The intended trick is meet in the middle: cut the array into two halves, list the subset sums of each half, and then match them up.
Pick n elements for one side
Constraints
- ●
1 <= n <= 15 - ●
nums.length == 2 * n - ●
-10^7 <= nums[i] <= 10^7
Examples
nums = [3,9,7,3]2nums = [-36,36]72nums = [2,-1,0,4,-2,-9]0Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Salesforce | Hard | View all Salesforce questions → |
How to Think About It
Brute force: generate all subsets of size n from 2n elements. There are C(2n, n) such subsets, which is exponential. For each subset, compute the sum of both halves and track the minimum difference. Too slow for n >= 15.
Key insight: split the array into two halves of n/2 elements each. Generate all possible subset sums for the left half and right half separately. This reduces the problem to combining two smaller subproblems.
Meet in the middle: for the left half, generate all 2^(n/2) subset sums. For each subset size k, the right half must contribute n-k elements. For each possible k, sort the right half's subset sums for each subset size. Use binary search to find the complement that minimizes the difference.
Optimization: for each subset size from the left half, sort the corresponding subset size sums from the right half. Use binary search to find the value closest to (target - left_sum). This gives O(2^(n/2) * n) complexity instead of O(2^n).
Optimal Approach
Step 1: Split the array into left half (first n/2) and right half (remaining).
Step 2: Generate all subset sums for the left half, grouped by subset size. Store as left[size] = sorted list of sums.
Step 3: Generate all subset sums for the right half, grouped by subset size. Store as right[size] = sorted list of sums.
Step 4: For each subset size k from 0 to n:
- Get left sums for size k and right sums for size n-k
- For each left_sum, use binary search on right_sums to find the value closest to (total/2 - left_sum)
- Update the minimum difference
Step 5: Return the minimum difference found.
Walkthrough for [1, 2, 3, 4, 5, 6] (n=3, total=21):
- Left = [1,2,3], Right = [4,5,6]
- For k=1, need 2 from right. Left sums of size 1: [1, 2, 3]. Right sums of size 2: [9, 10, 11].
- For left_sum=1, best right_sum = 10 (target=10). Diff = |21 - 2*(1+10)| = 1.
- Result: 1 (partition [1,4,5] and [2,3,6] with sums 10 and 11).
Time: O(2^(n/2) * n) for generating and combining subset sums. Space: O(2^(n/2)) for storing subset sums.
Meet in the middle
What Trips People Up in Real Interviews
Trying a brute force DP approach. A standard knapsack won't work because you need exactly n elements in each partition, not just any subset with sum close to target. The "exactly n elements" constraint makes meet-in-the-middle the right approach.
Forgetting to group subset sums by subset size. When the left half takes k elements, the right half must take n-k elements. You cannot mix subset sums of different sizes. Group them separately.
Not using binary search after sorting. Once you sort the right half's subset sums for each size, binary search is what makes the solution efficient. Without it, you're back to O(2^n).
Confusing the target sum. The total sum of all elements is fixed. You want to split into two groups with sum as close to total/2 as possible. The minimum difference is total - 2*best_sum.
Integer overflow with large sums. The problem says elements can be up to 10^7 and n up to 15, so the total sum can be up to 3*10^8. Use long long in C++ or long in Java to avoid overflow.
Solution Code
O(2^(n/2) * n) timeimport bisect
def minimumDifference(nums):
total = sum(nums)
n = len(nums) // 2
half = n
def get_subset_sums(arr):
size = len(arr)
subsets = [[] for _ in range(size + 1)]
for mask in range(1 << size):
s = 0
bits = 0
for i in range(size):
if mask & (1 << i):
s += arr[i]
bits += 1
subsets[bits].append(s)
for i in range(size + 1):
subsets[i].sort()
return subsets
left = get_subset_sums(nums[:n])
right = get_subset_sums(nums[n:])
min_diff = total
for k in range(n + 1):
for ls in left[k]:
target = total // 2 - ls
j = bisect.bisect_left(right[n - k], target)
for idx in [j - 1, j]:
if 0 <= idx < len(right[n - k]):
rs = right[n - k][idx]
diff = abs(total - 2 * (ls + rs))
min_diff = min(min_diff, diff)
return min_diffFrequently Asked Questions
What is the Partition Array Into Two Arrays to Minimize Sum Difference problem?
Partition an array of 2n elements into two groups of n elements each such that the absolute difference between their sums is minimized. This problem requires the meet-in-the-middle technique to achieve exponential optimization over brute force.
How do you solve Partition Array Into Two Arrays to Minimize Sum Difference?
The optimal approach runs in O(2^(n/2) * n) time and O(2^(n/2)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Partition Array Into Two Arrays to Minimize Sum Difference?
Partition Array Into Two Arrays to Minimize Sum Difference is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Partition Array Into Two Arrays to Minimize Sum Difference?
- Trying a brute force DP approach. A standard knapsack won't work because you need exactly n elements in each partition, not just any subset with sum close to target. The "exactly n elements" constraint makes meet-in-the-middle the right approach.
- Forgetting to group subset sums by subset size. When the left half takes k elements, the right half must take n-k elements. You cannot mix subset sums of different sizes. Group them separately.
- Not using binary search after sorting. Once you sort the right half's subset sums for each size, binary search is what makes the solution efficient. Without it, you're back to `O(2^n)`.
- Confusing the target sum. The total sum of all elements is fixed. You want to split into two groups with sum as close to total/2 as possible. The minimum difference is `total - 2*best_sum`.
- Integer overflow with large sums. The problem says elements can be up to 10^7 and n up to 15, so the total sum can be up to 3*10^8. Use `long long` in C++ or `long` in Java to avoid overflow.