1755. 最接近目标值的子序列和

1755. 最接近目标值的子序列和

选出一个子集，子集的和满足某个要求，用状态压缩dp。
当n过大时，比如本题的n <=40，可以把数组nums划分成左右两部分，left和right，分别求子集和。
答案就在：

1. left构成的一个子集和中
2. right构成的一个子集和中
3. left中选择一个，right中选择一个，两个的和是目标结果

其中第3条可以用双指针解决。

这样问题的复杂度从降低至
因为求left子集和时，需要
求right子集和时，需要
最后双指针需要
最终复杂度为

高度相似题：805. 数组的均值分割，还是本题简单一点，我是看了1755才会的805

class Solution {
 public:
  int minAbsDifference(vector<int>& nums, int goal) {
    int n = nums.size();
    vector<int> left, right;
    for (int i = 0; i < n / 2; i++) left.push_back(nums[i]);
    for (int i = n / 2; i < n; i++) right.push_back(nums[i]);

    int n1 = left.size(), n2 = right.size();
    int lsum[1 << n1], rsum[1 << n2];
    memset(lsum, 0, sizeof lsum);
    memset(rsum, 0, sizeof rsum);
    for (int i = 0; i < 1 << n1; i++)
      for (int j = 0; j < n1; j++)
        if (i & (1 << j)) lsum[i] = lsum[i ^ (1 << j)] + left[j];
    for (int i = 0; i < 1 << n2; i++)
      for (int j = 0; j < n2; j++)
        if (i & (1 << j)) rsum[i] = rsum[i ^ (1 << j)] + right[j];

    int res = INT_MAX;
    for (int i = 0; i < n1; i++) res = min(res, abs(lsum[i] - goal));
    for (int i = 0; i < n2; i++) res = min(res, abs(rsum[i] - goal));

    sort(lsum, lsum + (1 << n1));
    sort(rsum, rsum + (1 << n2));

    int i = 0, j = (1 << n2) - 1;
    while (i < (1 << n1) && j >= 0) {
      int s = lsum[i] + rsum[j];
      res = min(res, abs(goal - s));
      if (s > goal) j--;
      else i++;
    }
    return res;
  }
};