题目描述

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

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

样例

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

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

输入：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
• -10^7 <= nums[i] <= 10^7

算法

(折半枚举 + 二分) $O(n \cdot 2^n)$

1. 分别枚举前 $n$ 个数字，与后 $n$ 个数字的组合情况，用二维数组 $s1$ 和 $s2$ 记录，其中 $s1(x)$ 表示在前 $n$ 个数字中，选了 $x$ 个数字作为第一个数组的所有差值情况。$s2$ 同理。
2. 接下来按照 $x$ 的顺序枚举 $s1$ 数组的每一个差值情况 $d$，对于 $x$，需要找 $s2(n - x)$ 的差值情况。为了尽可能使得差值最小，可以提前将 $s2(n - y)$ 从小到大排序，然后二分查找最接近 $-d$ 的两个值，并更新答案。

时间复杂度

• 折半枚举的时间复杂度为 $O(2^n)$。
• 排序 $s2$ 数组需要 $O(n \cdot 2^n)$ 的时间。
• $s1$ 中共有 $2^n$ 种情况，对于每一种情况，需要 $O(\log (2^n)) = O(n)$ 的时间二分查找。
• 故总时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 需要 $O(2^n)$ 的额外空间存储折半枚举的差值情况。

C++ 代码

class Solution {
private:
    void solve(int i, int x, int diff,
    vector<vector<int>> &s, const vector<int> &nums) {
        if (i == nums.size()) {
            s[x].push_back(diff);
            return;
        }

        solve(i + 1, x, diff - nums[i], s, nums);
        solve(i + 1, x + 1, diff + nums[i], s, nums);
    }

public:
    int minimumDifference(vector<int>& nums) {
        const int n = nums.size() / 2;

        vector<vector<int>> s1(n + 1), s2(n + 1);
        solve(0, 0, 0, s1, vector<int>(nums.begin(), nums.begin() + n));
        solve(0, 0, 0, s2, vector<int>(nums.begin() + n, nums.end()));

        for (int y = 0; y <= n; y++)
            sort(s2[y].begin(), s2[y].end());

        int ans = INT_MAX;
        for (int x = 0; x <= n; x++) {
            int y = n - x;
            auto &s = s2[y];

            for (int diff : s1[x]) {
                int l = 0, r = s.size();
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if (s[mid] >= -diff) r = mid;
                    else l = mid + 1;
                }

                if (l != s.size())
                    ans = min(ans, abs(diff + s[l]));
                if (l > 0)
                    ans = min(ans, abs(diff + s[l - 1]));
            }
        }

        return ans;
    }
};