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 [1], I realized this technology’s name is meet in middle

[2] 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[3][4]

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
two parts difference: AAA + DD - CCC - BB
         if we cut into two parts, we get:
         AAA - BB for first half
         CCC - DD for the scecond half. Then
         AAA + DD - CCC - BB = AAA - BB - (CCC - DD)
        */
        int ret = INT_MAX;
        for (int i = 0; i <=n; ++i){
            for (auto x: l[i]){
                auto it = lower_bound(r[i].begin(), r[i].end(), x);
                if (it != r[i].begin()){
                    ret = min(ret, abs(x - *(prev(it))));
                }
                if (it != r[i].end()){
                    ret = min(ret, abs(x - *it));
                }
            }
        }
        return ret;
}
};

Reference

[1] https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/discuss/1513298/C++-Meet-In-Middle

[2] https://www.geeksforgeeks.org/meet-in-the-middle/

[3] zerotrac2’s submission of LC 262 weekly contest

[4]cuiaoxiang’s submission of LC 262 weekly contest