(状态压缩+折半)2035. 将数组分成两个数组并最小化数组和的

2035. 将数组分成两个数组并最小化数组和的差

状态压缩+折半后用双指针

class Solution {
 public:
  vector<int> v1[20], v2[20];
  void get(vector<int> v[20], vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < 1 << n; i++) {
      int sum = 0, cnt = 0;
      for (int j = 0; j < n; j++) {
        if (i & (1 << j))
          sum += arr[j], cnt++;
      }
      v[cnt].push_back(sum);
    }
    for (int i = 0; i <= n; i++) sort(v[i].begin(), v[i].end());
  }
  int minimumDifference(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int n = nums.size();
    vector<int> arr(n / 2);
    for (int i = 0; i < n / 2; i++) arr[i] = nums[i];
    get(v1, arr);
    for (int i = 0; i < n / 2; i++) arr[i] = nums[i + n / 2];
    get(v2, arr);
    int res = INT_MAX;
    for (int i = 0; i <= n / 2; i++) {
      int l = 0, r = (int)v2[n / 2 - i].size() - 1;
      if (v1[i].size() == 0) res = min(res, abs(sum - 2 * v2[n / 2 - i][0]));
      if (v2[n / 2 - i].size() == 0) res = min(res, abs(sum - 2 * v1[i][0]));
      while (l < v1[i].size() && r >= 0) {
        int lsum = v1[i][l] + v2[n / 2 - i][r];
        int rsum = sum - lsum;
        res = min(res, abs(lsum - rsum));
        if (lsum < rsum)
          l++;
        else
          r--;
      }
    }
    return res;
  }
};