2035. Partition Array Into Two Arrays to Minimize Sum Difference

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.

• Time : O(2^n * log(2^n))
• Space : O(2^n)

c++

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        if(nums.size() == 2) return abs(nums[0] - nums[1]);
        int sum = accumulate(nums.begin(), nums.end(), 0), sz = nums.size(), res = INT_MAX;
        int half = sz / 2;
        
        vector<int> left[sz/2], right[sz/2];
        for(int i = 0; i < half; i++) {
            for(int j = i - 1; j >= 0; j--) {
                for(auto n : left[j]) {
                    left[j + 1].push_back(n + nums[i]);
                }
                for(auto n : right[j]) {
                    right[j + 1].push_back(n + nums[i + half]);
                }
            }
            left[0].push_back(nums[i]);
            right[0].push_back(nums[i + half]);
        }
        for(int i = 0; i < half; i++)
            sort(right[i].begin(), right[i].end());
        res = abs(sum - left[half-1].back() * 2);
        for(int i = 0, j = half - 2; i < half - 1; i++, j--) {
            for(auto n : left[i]) {
                int A = n, B = sum - A;
                auto& r = right[j];
                auto it = lower_bound(r.begin(), r.end(), (B-A)/2);
                if(it != end(r))
                    res = min(res, abs(B-A-*it*2));
                if(it != begin(r))
                    res = min(res, abs(B-A-*prev(it)*2));
            }
        }
        return res;
    }
};