Partition Array Into Two Arrays to Minimize Sum Difference
HardPrompt
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] <= 107
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to partition the array nums into two subarrays of size n. We can use recursion to generate every possible subset of size n for the first array. For each such partition, we calculate the sum of both arrays and find their absolute difference. We keep track of the minimum difference found across all partitions.
Algorithm
- Calculate
totalSumof all elements innums. - Initialize
minDifferenceto a very large value. - Define a recursive function
solve(index, count, sum1):- If
count == n:sum2 = totalSum - sum1.minDifference = min(minDifference, abs(sum1 - sum2)).- Return.
- If
index == 2*n:- Return.
- To avoid TLE, add pruning: if the number of elements we still need to pick (
n - count) is greater than the number of elements remaining in the array (2*n - index), we can prune this path. - Include
nums[index]: Callsolve(index + 1, count + 1, sum1 + nums[index]). - Exclude
nums[index]: Callsolve(index + 1, count, sum1).
- If
- Call
solve(0, 0, 0). - Return
minDifference.
Walkthrough
The problem is to find a subset of n elements from the 2*n elements such that its sum, let's call it sum1, makes the value | (totalSum - sum1) - sum1 | = |totalSum - 2 * sum1| as small as possible. We can define a recursive function, say findMinDiff(index, count, currentSum), which tries to build the first partition.
index: The current index in thenumsarray we are considering.count: The number of elements already chosen for the first partition.currentSum: The sum of elements chosen so far.
The recursion explores two choices for each element: either include it in the first partition or not. The base case for the recursion is when we have chosen n elements (count == n). At this point, we have a valid partition, and we calculate the difference |totalSum - 2 * currentSum| and update our global minimum. We also need pruning conditions to avoid unnecessary computations. For example, if the number of elements left to choose from is less than the number of elements we still need to pick, we can stop that recursive path.
class Solution { int minDiff = Integer.MAX_VALUE; int totalSum = 0; int n; public int minimumDifference(int[] nums) { this.n = nums.length / 2; for (int num : nums) { this.totalSum += num; } findMinDiff(0, 0, 0, nums); return minDiff; } private void findMinDiff(int index, int count, int currentSum, int[] nums) { // Pruning: if remaining elements are not enough to form a partition of size n if (n - count > nums.length - index) { return; } if (count == n) { int sum2 = totalSum - currentSum; minDiff = Math.min(minDiff, Math.abs(currentSum - sum2)); return; } if (index == nums.length) { return; } // Include nums[index] findMinDiff(index + 1, count + 1, currentSum + nums[index], nums); // Exclude nums[index] findMinDiff(index + 1, count, currentSum, nums); }}Complexity
Time
O(C(2*n, n)). The recursion tree explores all combinations of choosing `n` elements from `2*n`. For `n=15`, `C(30, 15)` is approximately `1.55 * 10^8`, which is very slow.
Space
O(n) for the recursion stack depth, as the maximum depth of the recursion is `2*n`.
Trade-offs
Pros
Simple to understand and implement.
It's a direct translation of the problem statement.
Cons
Extremely inefficient for the given constraints.
Will likely result in a "Time Limit Exceeded" error on most platforms.
This approach significantly improves upon the brute-force method by using a divide-and-conquer strategy known as "meet-in-the-middle". The array nums of size 2*n is split into two halves, each of size n. We generate all possible subset sums for both halves independently. Then, we combine the sums from the two halves to find the partition that minimizes the sum difference.
Algorithm
- Split
numsinto two halves,left_partandright_part, each of sizen. - For
left_part, generate all possible subset sums for each possible subset size (0ton). Store them inleft_sums, whereleft_sums[k]is a set of sums of subsets of sizek. - Do the same for
right_partand store them inright_sums. - Calculate
totalSum. Initializemin_diffto infinity. - Iterate
kfrom0ton.- Let
sums1be the list of sums fromleft_sums[k]. - Let
sums2be the list of sums fromright_sums[n-k]. - Sort
sums2. - For each
s1insums1:- Calculate the target for the second sum:
target_s2 = (totalSum / 2) - s1. - Use binary search on
sums2to find the value closest totarget_s2. Let this bes2. - The partition sum is
S = s1 + s2. - Update
min_diff = min(min_diff, abs(totalSum - 2 * S)).
- Calculate the target for the second sum:
- Let
- Return
min_diff.
Walkthrough
The core idea is to reduce the exponential complexity from O(C(2n, n)) to O(n * 2^n). First, we split the nums array into a left_half (first n elements) and a right_half (last n elements). Next, we generate all possible sums for subsets of any size k (from 0 to n) for both halves. We can store these sums in a list of sets, where sums[k] contains all possible sums of k elements. This generation can be done with a recursive function, taking O(2^n) time for each half.
Our goal is to form a partition of size n with a sum S that is as close as possible to totalSum / 2. This partition will be formed by picking k elements from the left_half and n-k elements from the right_half. We iterate through k from 0 to n. For each k, we take a sum s1 from left_sums[k]. We then need to find a sum s2 from right_sums[n-k] such that s1 + s2 is closest to totalSum / 2. This is equivalent to finding s2 closest to (totalSum / 2) - s1. To find the closest s2 efficiently, we can sort the list of sums from right_sums[n-k] and use binary search for each s1. For each combination of s1 and s2, we calculate the partition sum S = s1 + s2 and update our minimum difference with |totalSum - 2*S|.
import java.util.*; class Solution { public int minimumDifference(int[] nums) { int n = nums.length / 2; int totalSum = 0; for (int num : nums) { totalSum += num; } List<Set<Integer>> leftSums = new ArrayList<>(); for (int i = 0; i <= n; i++) { leftSums.add(new HashSet<>()); } generate(0, 0, 0, nums, n, leftSums); List<Set<Integer>> rightSums = new ArrayList<>(); for (int i = 0; i <= n; i++) { rightSums.add(new HashSet<>()); } generate(n, 0, 0, nums, 2 * n, rightSums); int minDiff = Integer.MAX_VALUE; for (int k = 0; k <= n; k++) { List<Integer> s1List = new ArrayList<>(leftSums.get(k)); List<Integer> s2List = new ArrayList<>(rightSums.get(n - k)); Collections.sort(s2List); for (int s1 : s1List) { int targetS2 = (totalSum / 2) - s1; int idx = Collections.binarySearch(s2List, targetS2); if (idx >= 0) { int partitionSum = s1 + s2List.get(idx); minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum)); } else { int insertionPoint = -idx - 1; if (insertionPoint < s2List.size()) { int partitionSum = s1 + s2List.get(insertionPoint); minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum)); } if (insertionPoint > 0) { int partitionSum = s1 + s2List.get(insertionPoint - 1); minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum)); } } } } return minDiff; } private void generate(int index, int count, int currentSum, int[] nums, int end, List<Set<Integer>> sums) { if (index == end) { sums.get(count).add(currentSum); return; } // Exclude nums[index] generate(index + 1, count, currentSum, nums, end, sums); // Include nums[index] generate(index + 1, count + 1, currentSum + nums[index], nums, end, sums); }}Complexity
Time
O(n * 2^n). Generating the sums for each half takes `O(2^n)`. The combination step involves iterating through `k` from `0` to `n`. For each `k`, we iterate through `C(n, k)` sums and perform a binary search on a list of size `C(n, n-k)`. The total time is dominated by `sum_{k=0 to n} C(n, k) * log(C(n, k))`, which is roughly `O(n * 2^n)`.
Space
O(2^n). We need to store all possible subset sums for both halves. The total number of sums is `2 * sum_{k=0 to n} C(n, k) = 2 * 2^n`.
Trade-offs
Pros
Much more efficient than brute force and feasible for the given constraints (
n <= 15).A classic and powerful technique for problems with this structure and input size.
Cons
More complex to implement than the brute-force approach.
Requires significant memory to store the subset sums.
Solutions
Solution
class Solution {public int minimumDifference(int[] nums) { int n = nums.length >> 1; Map<Integer, Set<Integer>> f = new HashMap<>(); Map<Integer, Set<Integer>> g = new HashMap<>(); for (int i = 0; i < (1 << n); ++i) { int s = 0, cnt = 0; int s1 = 0, cnt1 = 0; for (int j = 0; j < n; ++j) { if ((i & (1 << j)) != 0) { s += nums[j]; ++cnt; s1 += nums[n + j]; ++cnt1; } else { s -= nums[j]; s1 -= nums[n + j]; } } f.computeIfAbsent(cnt, k->new HashSet<>()).add(s); g.computeIfAbsent(cnt1, k->new HashSet<>()).add(s1); } int ans = Integer.MAX_VALUE; for (int i = 0; i <= n; ++i) { List<Integer> fi = new ArrayList<>(f.get(i)); List<Integer> gi = new ArrayList<>(g.get(n - i)); Collections.sort(fi); Collections.sort(gi); for (int a : fi) { int left = 0, right = gi.size() - 1; int b = -a; while (left < right) { int mid = (left + right) >> 1; if (gi.get(mid) >= b) { right = mid; } else { left = mid + 1; } } ans = Math.min(ans, Math.abs(a + gi.get(left))); if (left > 0) { ans = Math.min(ans, Math.abs(a + gi.get(left - 1))); } } } return ans; }}class Solution {public: int minimumDifference(vector<int> &nums) { int n = nums.size() >> 1; vector<vector<int>> f(n + 1), g(n + 1); for (int i = 0; i < (1 << n); ++i) { int s = 0, cnt = 0; int s1 = 0, cnt1 = 0; for (int j = 0; j < n; ++j) { if (i & (1 << j)) { s += nums[j]; ++cnt; s1 += nums[n + j]; ++cnt1; } else { s -= nums[j]; s1 -= nums[n + j]; } } f[cnt].push_back(s); g[cnt1].push_back(s1); } for (int i = 0; i <= n; ++i) { sort(f[i].begin(), f[i].end()); sort(g[i].begin(), g[i].end()); } int ans = INT_MAX; for (int i = 0; i <= n; ++i) { for (int a : f[i]) { int left = 0, right = g[n - i].size() - 1; int b = -a; while (left < right) { int mid = (left + right) >> 1; if (g[n - i][mid] >= b) right = mid; else left = mid + 1; } ans = min(ans, abs(a + g[n - i][left])); if (left > 0) ans = min(ans, abs(a + g[n - i][left - 1])); } } return ans; }};class Solution: # min(abs(f[i] + g[n - i])) for a in fi : left , right = 0 , len ( gi ) - 1 b = - a while left < right : mid = ( left + right ) >> 1 if gi [ mid ] >= b : right = mid else : left = mid + 1 ans = min ( ans , abs ( a + gi [ left ])) if left > 0 : ans = min ( ans , abs ( a + gi [ left - 1 ])) return ans def minimumDifference(self, nums: List[int]) -> int: n = len(nums) >> 1 f = defaultdict(set) g = defaultdict(set) for i in range(1 << n): s = cnt = 0 s1 = cnt1 = 0 for j in range(n): if (i & (1 << j)) != 0: s += nums[j] cnt += 1 s1 += nums[n + j] cnt1 += 1 else: s -= nums[j] s1 -= nums[n + j] f[cnt]. add(s) g[cnt1]. add(s1) ans = inf for i in range(n + 1): fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.