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] <= 107Problem Overview: You are given an array of 2n integers. Split it into two groups of size n so the absolute difference between their sums is minimized. The challenge is exploring combinations efficiently without enumerating all C(2n, n) possibilities.
Approach 1: Backtracking with Subset Sum / Meet-in-the-Middle (Time: O(n * 2^(n/2)), Space: O(2^(n/2)))
Brute forcing every partition is infeasible because the number of combinations grows exponentially. A better strategy splits the array into two halves and enumerates subset sums for each half using bitmask or backtracking. For the first half, store sums grouped by how many elements were chosen. Do the same for the second half. The total array sum is fixed, so you only need combinations that select exactly n elements across both halves.
For each subset sum from the first half, search the second-half sums that bring the total as close as possible to totalSum / 2. Sorting the second-half sums allows fast lookup using binary search. This technique is a classic meet-in-the-middle optimization: generate 2^(n/2) subsets instead of 2^n. The best candidate minimizes |totalSum - 2 * chosenSum|. The approach heavily relies on efficient subset enumeration and grouping by subset size.
Approach 2: Dynamic Programming with Subset Sum (Time: O(n * S), Space: O(S))
This method treats the problem as a balanced subset sum. The goal is to pick exactly n elements whose sum is as close as possible to totalSum / 2. Using dynamic programming, maintain states representing achievable sums with a given number of elements. Transition by either including or excluding each number.
The DP table tracks dp[count][sum], meaning whether a subset of count elements can produce a given sum. After processing all numbers, examine sums reachable with exactly n elements and pick the one closest to half of the total. This approach is conceptually simple but becomes expensive when the sum range is large, which is why meet-in-the-middle is typically preferred.
Recommended for interviews: The meet-in-the-middle subset enumeration is the expected solution for this problem. It demonstrates strong understanding of exponential optimization, array partitioning strategies, and efficient search with binary search. A plain subset DP shows the correct problem framing but struggles with large numeric ranges.
In this approach, we use a backtracking method to generate all possible partitions of the array into two subarrays of equal size. We then calculate the sum of the elements in each subarray and find the minimum absolute difference between these sums.
Generate all possible combinations for dividing the array elements into two subarrays of size n, leveraging backtracking techniques. For each valid partition, compute the sum of both subarrays and determine the absolute difference. Continue this process while tracking the minimum absolute difference encountered.
This C implementation employs a backtracking technique to explore all subsets of the array of size n. For each subset, it calculates the complement set and checks the absolute difference of their sums. By iterating over all possibilities, it ensures that the minimum absolute difference is achieved. The solution tracks this value through recursion.
Time Complexity: O(2^n) due to recursive subset creation.
Space Complexity: O(n) because of the recursion call stack space.
This approach utilizes dynamic programming to solve the subset sum problem for optimization. It determines the possible sum values that can be achieved by selecting subsets from the input array. With a goal of minimizing the absolute difference of the two partitions, the best achievable partition is directly extracted from the possible sums identified by the DP array.
Divide the array into two. For each half, build an array of all possible subset sums. Use a combination of these to get the closest possible sum to half of the total. Used efficiently, the technique ensures the minimum difference.
The C code defines a dynamic programming approach for subset sum determination, aiming to achieve close sums to half the total sum. A bottom-up approach is used for filling up the dp array, and finally, the minimum difference is extracted from the dp results.
Time Complexity: O(n * sum), where sum is total of the array.
Space Complexity: O(sum).
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Subset Sum | Time Complexity: O(2^n) due to recursive subset creation. |
| Approach 2: Dynamic Programming and Subset Sum | Time Complexity: O(n * sum), where sum is total of the array. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / Meet-in-the-Middle Subset Sums | O(n * 2^(n/2)) | O(2^(n/2)) | Best practical solution when n ≤ 15 per half; typical interview and competitive programming approach |
| Dynamic Programming Subset Sum | O(n * S) | O(S) | Works when total sum range is small and memory allows DP over sums |
Meet in the Middle | 2035. Partition Array Into Two Arrays to Minimize Sum Difference | Day 022 • Aryan Mittal • 34,171 views views
Watch 9 more video solutions →Practice Partition Array Into Two Arrays to Minimize Sum Difference with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor