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.
Example 1:
Input: nums = [3,9,7,3] Output: 2 Explanation: One optimal partition is: [3,9] and [7,3]. The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.
Example 2:
Input: nums = [-36,36] Output: 72 Explanation: One optimal partition is: [-36] and [36]. The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.
Example 3:
Input: nums = [2,-1,0,4,-2,-9] Output: 0 Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2]. The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.
Constraints:
1 <= n <= 15nums.length == 2 * n-107 <= nums[i] <= 107The key challenge in #2035 Partition Array Into Two Arrays to Minimize Sum Difference is splitting the array into two groups of equal size such that the absolute difference of their sums is minimized. Since the array length is 2n, a brute-force search over all subsets would take O(2^(2n)), which is infeasible.
A more efficient strategy uses the meet-in-the-middle technique. Split the array into two halves of size n. For each half, generate all subset sums grouped by the number of selected elements using bitmasking. Then, for every subset from the first half, use binary search on the sorted subset sums of the second half to find the value that brings the total closest to half of the overall array sum.
This combination of bitmask generation, sorting, and binary search significantly reduces the search space while maintaining accuracy. The approach balances enumeration and efficient lookup to approximate the optimal partition.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Meet-in-the-Middle with Bitmask + Binary Search | O(n * 2^(n/2)) | O(2^(n/2)) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
The target sum for the two partitions is sum(nums) / 2.
Could you reduce the time complexity if you arbitrarily divide nums into two halves (two arrays)? Meet-in-the-Middle?
For both halves, pre-calculate a 2D array where the kth index will store all possible sum values if only k elements from this half are added.
For each sum of k elements in the first half, find the best sum of n-k elements in the second half such that the two sums add up to a value closest to the target sum from hint 1. These two subsets will form one array of the partition.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Meet-in-the-middle reduces the exponential search space by splitting the array into two halves and processing them separately. Instead of evaluating all 2^(2n) subsets, the algorithm works with about 2^(n/2) subsets for each half, making the problem tractable.
Yes, this problem represents a classic hard-level interview question involving meet-in-the-middle, subset enumeration, and binary search optimization. Variants of this partitioning and subset-sum style problem have appeared in FAANG-level coding interviews.
The optimal approach uses a meet-in-the-middle strategy. The array is split into two halves, all subset sums are generated using bitmasking, and binary search is used to find combinations that minimize the difference between the two partitions.
Commonly used structures include arrays or vectors to store subset sums grouped by subset size, and sorted lists to enable binary search. Bitmasking is also used to efficiently generate all subsets of each half.