给你一个长度为 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
-10^7 <= nums[i] <= 10^7
思路：最直接的方法是采用二进制状压枚举的方式，并将所有二进制表示中1的个数为n/2的状态拿出来判断两个数组的差，其代码如下【超时】：
class Solution {
public int minimumDifference(int[] nums) {
int ans = Integer.MAX_VALUE;
int n = nums.length, sum = 0;
n /= 2;
for (int i = 0; i < 2 * n; i++)
sum += nums[i];
for (int s = (1 << n) - 1, u = 1 << (2 * n); s < u; ) {
int tmp = 0;
for (int i = 0; i < 2 * n; i++) {
if ((s >> i & 1) != 0)
tmp += nums[i];
}
ans = Math.min(ans, Math.abs(sum - 2 * tmp));
int b = s & -s;
s = (s + b) | (((s ^ (s + b)) >> 2) / b);
}
return ans;
}
}
考虑进一步优化，由于题目中2*n的大小为30，因此我们可以采用折半二进制状压枚举的方式，首先将原数组一分为二，并分别对每一个子数组进行枚举，对于二进制表示中为1的对应元素作为第一个人的选择，剩下的元素为第二个人的选择，并分别保存两个数组中对应1的个数所组成的两数组和的差值，将其从小到大排序。之后对于第一个子数组的所有状态，我们根据其二进制表示中1的个数i，在第二个数组中对应二进制表示1的个数为n-i的所有差值中二分查找，保证组成的和的差值最小。【详见代码】：
class Solution {
public int minimumDifference(int[] nums) {
int ans = Integer.MAX_VALUE;
int n = nums.length;
n /= 2;
int[] arr1 = new int[n];
int[] arr2 = new int[n];
for (int i = 0; i < n; i++)
arr1[i] = nums[i];
for (int i = n; i < 2 * n; i++)
arr2[i - n] = nums[i];
List> e1 = work(arr1, n);
List> e2 = work(arr2, n);
for (int i = 0; i <= n; i++) {
int size = e1.get(i).size();
for (int j = 0; j < size; j++) {
int now = e1.get(i).get(j), l = 0, r = e2.get(n - i).size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
//System.out.println(e2.get(n - i).get(mid) + " " + e1.get(i).get(j));
if (e2.get(n - i).get(mid) + e1.get(i).get(j) <= 0) {
ans = Math.min(ans, Math.abs(e2.get(n - i).get(mid) + e1.get(i).get(j)));
l = mid + 1;
} else {
ans = Math.min(ans, Math.abs(e2.get(n - i).get(mid) + e1.get(i).get(j)));
r = mid - 1;
}
}
}
}
return ans;
}
private List> work(int[] arr, int n) {
int sum = 0;
List> e = new ArrayList<>();
for (int i = 0; i <= n; i++)
e.add(new ArrayList<>());
for (int i = 0; i < n; i++)
sum += arr[i];
for (int i = 0; i < (1 << n); i++) {
int num = 0, tmp = 0;
for (int j = 0; j < n; j++) {
if ((i >> j & 1) != 0) {
num++;
tmp += arr[j];
}
}
e.get(num).add(2 * tmp - sum);
}
for (int i = 0; i <= n; i++)
Collections.sort(e.get(i));
return e;
}
}
