Partition Array Into Two Arrays to Minimize Sum Difference
Partition Array Into Two Arrays to Minimize Sum Difference is a hard recursion & backtracking problem solved with the meet in the middle pattern.
The best approach, optimal (meet in the middle), runs in O(2^n · n) time and O(2^n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pick / not pick) up.
Problem
You are given an integer array nums of even length 2 * n. Split it into two arrays of exactly n elements each, so that every element goes into exactly one of them.
Return the smallest possible absolute difference between the sums of the two arrays.
Examples
Example 1
- Input
nums = [5, 9, 2, 6]- Output
0- Why
- Split into [5, 6] and [9, 2]: both sum to 11.
Example 2
- Input
nums = [-8, 4]- Output
12- Why
- Each half holds one number, so the only split gives |-8 - 4| = 12.
Example 3
- Input
nums = [10, -3, 7, 1, -6, 2]- Output
1- Why
- The total is 11, which is odd, so 0 is impossible. [10, 1, -6] sums to 5 and [-3, 7, 2] sums to 6.
Constraints
1 <= n <= 15nums.length == 2 * n-10^7 <= nums[i] <= 10^7
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (pick / not pick) | O(2^(2n)) | O(n) |
| Optimal (meet in the middle) | O(2^n · n) | O(2^n) |
1Brute force (pick / not pick)
O(2^(2n))Up to two choices for each of the 2n elements; pruning only trims the tree to about C(2n, n) leaves.O(n)The recursion depth is 2n.Decide for every element whether it goes into the first half, keeping a count and a running sum. When all elements are decided and exactly n were picked, the difference is |total - 2 * sum|. Prune branches that already picked too many or can no longer reach n.
- Compute total = sum of nums.
- dfs(i, count, sum): if count > n or count + (2n - i) < n, stop.
- At i == 2n, update best with |total - 2 * sum|.
- Otherwise recurse with nums[i] picked and not picked.
class Solution {
private int best;
public int minimumDifference(int[] nums) {
int total = 0;
for (int x : nums) total += x;
best = Integer.MAX_VALUE;
dfs(nums, 0, 0, 0, total);
return best;
}
private void dfs(int[] nums, int i, int count, int sum, int total) {
int m = nums.length, n = m / 2;
if (count > n || count + (m - i) < n) return;
if (i == m) {
best = Math.min(best, Math.abs(total - 2 * sum));
return;
}
dfs(nums, i + 1, count + 1, sum + nums[i], total);
dfs(nums, i + 1, count, sum, total);
}
}class Solution:
def minimumDifference(self, nums: List[int]) -> int:
m = len(nums)
n = m // 2
total = sum(nums)
best = float('inf')
def dfs(i: int, count: int, s: int) -> None:
nonlocal best
if count > n or count + (m - i) < n:
return
if i == m:
best = min(best, abs(total - 2 * s))
return
dfs(i + 1, count + 1, s + nums[i])
dfs(i + 1, count, s)
dfs(0, 0, 0)
return bestclass Solution {
public:
int minimumDifference(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
best = INT_MAX;
dfs(nums, 0, 0, 0, total);
return best;
}
private:
int best;
void dfs(vector<int>& nums, int i, int count, int sum, int total) {
int m = nums.size(), n = m / 2;
if (count > n || count + (m - i) < n) return;
if (i == m) {
best = min(best, abs(total - 2 * sum));
return;
}
dfs(nums, i + 1, count + 1, sum + nums[i], total);
dfs(nums, i + 1, count, sum, total);
}
};function minimumDifference(nums) {
const m = nums.length, n = m / 2;
let total = 0;
for (const x of nums) total += x;
let best = Infinity;
const dfs = (i, count, sum) => {
if (count > n || count + (m - i) < n) return;
if (i === m) {
best = Math.min(best, Math.abs(total - 2 * sum));
return;
}
dfs(i + 1, count + 1, sum + nums[i]);
dfs(i + 1, count, sum);
};
dfs(0, 0, 0);
return best;
}2Optimal (meet in the middle)
O(2^n · n)2^n sums per part; sorting them and doing one O(log 2^n) = O(n) binary search per left sum.O(2^n)The subset sums of both parts.Cut the array into a left part and a right part of n elements each. For each part, list the sums of all its subsets, grouped by how many elements they use. A valid first half takes c elements from the left and n - c from the right. For every left sum a with size c, we want a right sum b of size n - c that makes 2 * (a + b) as close to total as possible. With each right group sorted, binary search for the first b where 2 * (a + b) >= total and also check the one just before it.
- Enumerate all 2^n subset sums of the left part and of the right part, grouped by subset size (sum[mask] = sum[mask without its lowest bit] + that element).
- Sort every group of the right part.
- For each size c and each left sum a in group c, binary search group n - c of the right part for the first b with 2 * (a + b) >= total.
- Update the answer with |total - 2 * (a + b)| for that b and for its predecessor.
class Solution {
public int minimumDifference(int[] nums) {
int n = nums.length / 2, total = 0;
for (int x : nums) total += x;
List<List<Integer>> left = halfSums(nums, 0, n), right = halfSums(nums, n, n);
for (List<Integer> group : right) Collections.sort(group);
int best = Integer.MAX_VALUE;
for (int c = 0; c <= n; c++) {
List<Integer> r = right.get(n - c);
for (int a : left.get(c)) {
int lo = 0, hi = r.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (2 * (a + r.get(mid)) >= total) hi = mid;
else lo = mid + 1;
}
if (lo < r.size()) best = Math.min(best, Math.abs(total - 2 * (a + r.get(lo))));
if (lo > 0) best = Math.min(best, Math.abs(total - 2 * (a + r.get(lo - 1))));
}
}
return best;
}
private List<List<Integer>> halfSums(int[] nums, int start, int n) {
List<List<Integer>> bySize = new ArrayList<>();
for (int c = 0; c <= n; c++) bySize.add(new ArrayList<>());
int[] sum = new int[1 << n];
for (int mask = 0; mask < (1 << n); mask++) {
if (mask > 0) {
int low = Integer.numberOfTrailingZeros(mask);
sum[mask] = sum[mask & (mask - 1)] + nums[start + low];
}
bySize.get(Integer.bitCount(mask)).add(sum[mask]);
}
return bySize;
}
}class Solution:
def minimumDifference(self, nums: List[int]) -> int:
n = len(nums) // 2
total = sum(nums)
def half_sums(part: List[int]) -> List[List[int]]:
by_size = [[] for _ in range(n + 1)]
s = [0] * (1 << n)
for mask in range(1 << n):
if mask:
low = (mask & -mask).bit_length() - 1
s[mask] = s[mask & (mask - 1)] + part[low]
by_size[bin(mask).count("1")].append(s[mask])
return by_size
left = half_sums(nums[:n])
right = half_sums(nums[n:])
for group in right:
group.sort()
best = float('inf')
for c in range(n + 1):
r = right[n - c]
for a in left[c]:
lo, hi = 0, len(r)
while lo < hi:
mid = (lo + hi) // 2
if 2 * (a + r[mid]) >= total:
hi = mid
else:
lo = mid + 1
if lo < len(r):
best = min(best, abs(total - 2 * (a + r[lo])))
if lo > 0:
best = min(best, abs(total - 2 * (a + r[lo - 1])))
return bestclass Solution {
public:
int minimumDifference(vector<int>& nums) {
int n = nums.size() / 2, total = 0;
for (int x : nums) total += x;
vector<vector<int>> left = halfSums(nums, 0, n), right = halfSums(nums, n, n);
for (auto& group : right) sort(group.begin(), group.end());
int best = INT_MAX;
for (int c = 0; c <= n; c++) {
vector<int>& r = right[n - c];
for (int a : left[c]) {
int lo = 0, hi = r.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (2 * (a + r[mid]) >= total) hi = mid;
else lo = mid + 1;
}
if (lo < (int)r.size()) best = min(best, abs(total - 2 * (a + r[lo])));
if (lo > 0) best = min(best, abs(total - 2 * (a + r[lo - 1])));
}
}
return best;
}
private:
vector<vector<int>> halfSums(vector<int>& nums, int start, int n) {
vector<vector<int>> bySize(n + 1);
vector<int> sum(1 << n, 0);
for (int mask = 0; mask < (1 << n); mask++) {
if (mask > 0) {
int low = __builtin_ctz(mask);
sum[mask] = sum[mask & (mask - 1)] + nums[start + low];
}
bySize[__builtin_popcount(mask)].push_back(sum[mask]);
}
return bySize;
}
};function minimumDifference(nums) {
const n = nums.length / 2;
let total = 0;
for (const x of nums) total += x;
const halfSums = (start) => {
const bySize = Array.from({ length: n + 1 }, () => []);
const sum = new Array(1 << n).fill(0);
const bits = new Array(1 << n).fill(0);
for (let mask = 0; mask < (1 << n); mask++) {
if (mask > 0) {
const low = 31 - Math.clz32(mask & -mask);
sum[mask] = sum[mask & (mask - 1)] + nums[start + low];
bits[mask] = bits[mask & (mask - 1)] + 1;
}
bySize[bits[mask]].push(sum[mask]);
}
return bySize;
};
const left = halfSums(0), right = halfSums(n);
for (const group of right) group.sort((a, b) => a - b);
let best = Infinity;
for (let c = 0; c <= n; c++) {
const r = right[n - c];
for (const a of left[c]) {
let lo = 0, hi = r.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (2 * (a + r[mid]) >= total) hi = mid;
else lo = mid + 1;
}
if (lo < r.length) best = Math.min(best, Math.abs(total - 2 * (a + r[lo])));
if (lo > 0) best = Math.min(best, Math.abs(total - 2 * (a + r[lo - 1])));
}
}
return best;
}Edge cases to test
- n = 1: there is only one way to split
- Negative numbers, so sums are not monotone in the number of picked elements
- All values equal: the answer is 0
- An odd total: the answer is at least 1
Hints
Hint 1
If one half sums to s, the other sums to total - s, so the difference is |total - 2s|. You only have to choose the n elements of one half.
Hint 2
C(30, 15) is about 1.5 * 10^8 choices, too many. Split the array into a left and a right part of n elements each and enumerate subsets of each part separately (2^15 each).
Hint 3
If you take c elements from the left part, you must take n - c from the right. Group right-part sums by size, sort each group, and binary search for the sum that brings the total closest to total / 2.
FAQ
What is the best time complexity for Partition Array Into Two Arrays to Minimize Sum Difference?
Optimal (meet in the middle) runs in O(2^n · n) time and O(2^n) extra space. 2^n sums per part; sorting them and doing one O(log 2^n) = O(n) binary search per left sum.
Which pattern does Partition Array Into Two Arrays to Minimize Sum Difference use?
It is a recursion & backtracking problem that uses the meet in the middle pattern.
Is there a brute force solution for Partition Array Into Two Arrays to Minimize Sum Difference?
Yes. Brute force (pick / not pick) takes O(2^(2n)) time and O(n) space. Decide for every element whether it goes into the first half, keeping a count and a running sum.
Which edge cases should I test for Partition Array Into Two Arrays to Minimize Sum Difference?
n = 1: there is only one way to split; Negative numbers, so sums are not monotone in the number of picked elements; All values equal: the answer is 0; An odd total: the answer is at least 1.