[Leetcode]5897. 将数组分成两个数组并最小化数组和的差

【题目描述如下】

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回 最小 的数组和之差。

示例 1：

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
示例 2：

输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。
示例 3：

输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
 

提示：

1 <= n <= 15
nums.length == 2 * n
-107 <= nums[i] <= 107

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference
【题目分析】

刚开始看到这个题目，感觉很熟悉，状态压缩嘛，于是很开心的做了起来。代码如下：

class Solution {
public:
    /*
        每个数都有放在数组1或数组2两种选择，所以一共有2^2n-1中可能，由于是等分为两个数组，
        中间要去掉不能等分的；采用状态压缩法，用二进制表示每一种分组；
    */
    int BitCount(unsigned int n)
    {
        unsigned int c = 0 ;
        while (n > 0) {
            c += n & 1;
            n >>= 1;
        }
        return c ;
    }
    int CalcSum(vector<int>& nums, unsigned int n)
    {
        int res = 0;
        int i = 0;
        while (n > 0) {
            if (n & 1) {
                res += nums[i];
            }
            i++;
            n >>= 1;
        }
        return res;
    }
    int minimumDifference(vector<int>& nums) {
        int res = INT_MAX;
        int n = nums.size();
        vector<bool> rec((1 << n), false);
        for (int i = (1 << (n / 2)) - 1; i < 1 << n; i++) {
            if (BitCount(i) == n / 2) {
                // 求补集
                int left = i ^ ((1 << n) - 1);
                res = min(res, abs(CalcSum(nums, i) - CalcSum(nums, left)));
            } 
        }
        return res;
    }
};

每个数都有放在数组1或数组2两种选择，所以一共有2^2n-1中可能，由于是等分为两个数组，中间要去掉不能等分的；采用状态压缩法，用二进制表示每一种分组； 由于n最大为15，上述代码的时间复杂度O(2^2n)，代码会超时；

后来看了题解，发现使用分段的状态压缩和二分查找很巧妙地降低时间复杂度为O(n*2^n)；

代码分三步：

1）首先在前半段（n）进行状态枚举，每个数有两种情况：放到数组1，即加上其值；放到数组2，即减去其值。这样可以求出后半段的所有组合，存入数组f；

同理针对后半段采用同样的策略，将所有的组合放入数组g；

2）分别对f、g中的数组进行升序排列，以便后续二分查找；

3）所求最小差值为min(abs(f[i] + g[n-i]))，遍历每个f[i]，同时用二分法查找绝对值和最小的g[n-i]；

i + n - i = n表示等分的两个数组，每个有n个数；

代码如下：

class Solution {
public:
    /*
        每个数都有放在数组1或数组2两种选择，所以一共有2^2n-1中可能，由于是等分为两个数组，
        中间要去掉不能等分的；采用状态压缩法，用二进制表示每一种分组；
        由于n最大为15,O(2^2n)会导致代码超时；
        所以分成两段进行求解,将时间复杂度降至O(n*2^n);
    */
    int BitCount(unsigned int n)
    {
        unsigned int c = 0 ;
        while (n > 0) {
            c += n & 1;
            n >>= 1;
        }
        return c ;
    }

    int minimumDifference(vector<int>& nums) {
        int res = INT_MAX;
        int n = nums.size() / 2;
        vector<vector<int>> f(n + 1);
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < (1 << n); i++) {
            int cnt = BitCount(i);
            int j = 0;
            int sum = 0;
            int mask = i;
            while (j < n) {
                if (mask & 0x1) {
                    sum += nums[j];
                } else {
                    sum -= nums[j];
                }
                mask >>= 1;
                j++;
            }
            f[cnt].emplace_back(sum);
        }
        for (int i = 0; i < (1 << n); i++) {
            int cnt = BitCount(i);
            int j = 0;
            int sum = 0;
            int mask = i;
            while (j < n) {
                if (mask & 0x1) {
                    sum += nums[n + j];
                } else {
                    sum -= nums[n + j];
                }
                mask >>= 1;
                j++;
            }
            g[cnt].emplace_back(sum);
        }
        // 升序排列，为了方便后面二分查找
        for (int i = 0; i < n; i++) {
            sort(begin(f[i]), end(f[i]));
            sort(begin(g[i]), end(g[i]));
        }
        // 最小差值即为min(abs(f[i] + g[n-i]))
        for (int i = 0; i < n; i++) {
            for (auto& ft : f[i]) {
                // 查找大于等于-ft的，以便绝对值和最小
                auto it = lower_bound(begin(g[n - i]), end(g[n - i]), -ft);
                // 如果找到了
                if (it != end(g[n - i])) {
                    res = min(res, abs(ft + *it));
                }
                // 如果it == end没找到，则取最接近的
                if (it != begin(g[n - i])) {
                    res = min(res, abs(ft + *prev(it)));
                }
            }
        }
        return res;
    }
};