C++ meet in middle

2035. Partition Array Into Two Arrays to Minimize Sum Difference

Got stuck for the 4th questions of the last week’s weekly LC contest (LC 262 weekly contest). When review the top submissions, I found the technologies they used are pretty similar. Then I realized this should be some “common” pattern which I missed. Thanks for , I realized this technology’s name is meet in middle

 gave a very clear explanation for this technology. Basically, we have:

• Cut the problems into two halves
• Each half will have a problem size of 2^n where n is half of the total size.
• Solve each part and then combine the result.

The first time I used this strtegy should be for the 18. 4Sum problem.

Based on this, we can solve this problem with the complexity of

O(2^n log (2^n)) -> O(2^n * n)

Reference Code

class Solution {
public:
int minimumDifference(vector<int>& nums) {
const int n = nums.size() / 2;
vector<vector<int>> l(n+1), r(n+1);
// first half
for (int i = 0; i < (1<<n); ++i){
int cnt = __builtin_popcount(i);
int sum = 0;
for (int j = 0; j < n; ++j){
if ((1<<j) & i){
sum += nums[j];
} else {
sum -= nums[j];
}
}
l[cnt].push_back(sum);
}
// second half
for (int i = 0; i < (1<<n); ++i){
int cnt = __builtin_popcount(i);
int sum = 0;
for (int j = 0; j < n; ++j){
if ((1<<j) & i){
sum += nums[n + j];
} else {
sum -= nums[n + j];
}
}
r[cnt].push_back(sum);
}
for (int i = 0; i <= n; ++i){
sort(l[i].begin(), l[i].end());
sort(r[i].begin(), r[i].end());
}
// combine the first half and second half res
/*
How to combine the two parts result? Suppose we have the following pattern:
AAABB | CCCDD

Reference

 zerotrac2’s submission of LC 262 weekly contest

cuiaoxiang’s submission of LC 262 weekly contest