【折半处理 二分查找】1755. 最接近目标值的子序列和

class Solution {
public:
  int minAbsDifference(vector<int>& nums, int goal) {
    const int iHalf = nums.size() / 2;
    vector<int> vNum1 = Sum(nums.data(), iHalf);
    auto vNum2 = Sum(nums.data() + iHalf, nums.size() - iHalf);
    sort(vNum2.begin(), vNum2.end());
    int iRet = INT_MAX;
    for (const auto& n : vNum1) {
      auto it = std::lower_bound(vNum2.begin(), vNum2.end(), goal - n);
      if (vNum2.end() != it) {
        iRet = min(iRet, abs(goal - n - *it));
      }
      if (vNum2.begin() != it) {
        --it;
        iRet = min(iRet, abs(goal - n - *it));
      }
    }
    return iRet;
  }
  vector<int> Sum(int* p, int n) {
    vector<int> pre = { 0 };
    for (int i = 0; i < n; i++) {
      vector<int> dp = pre;
      for (const auto& iPre : pre) {
        dp.emplace_back(iPre + p[i]);
      }
      pre.swap(dp);
    }
    return pre;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  int goal;
  {
    Solution sln;
    nums = { 5, -7, 3, 5 }, goal = 6;
    auto res = sln.minAbsDifference(nums, goal);
    Assert(0, res);
  }
  {
    Solution sln;
    nums = { 7,-9,15,-2 }, goal =-5;
    auto res = sln.minAbsDifference(nums, goal);
    Assert(1, res);
  }
  {
    Solution sln;
    nums = { 1,2,3 }, goal = -7;
    auto res = sln.minAbsDifference(nums, goal);
    Assert(7, res);
  }
}

void CreateMaskVector(vector<int>& v,const int* const p,int n )
 {
   const int iMaxMaskNum = 1 << n;
   v.resize(iMaxMaskNum);
   for (int i = 0; i < n; i++)
   {
     v[1 << i] = p[i];
   }
   for (int mask = 1; mask < iMaxMaskNum ; mask++)
   {
     const int iSubMask = mask&(-mask);
     v[mask] = v[iSubMask] + v[mask-iSubMask];
   }
 }
 class Solution {
 public:
   int minAbsDifference(vector<int>& nums, int goal) {
     set<int> setLeft, setRight;
     setLeft.insert(0);
     setRight.insert(0);
     int iHalfNum = nums.size()/2;
     vector<int> vLeft,vRight;
     CreateMaskVector(vLeft, &*nums.begin(), iHalfNum);
     CreateMaskVector(vRight, &*nums.begin() + iHalfNum, nums.size() - iHalfNum);
     std::sort(vLeft.begin(), vLeft.end());
     std::sort(vRight.begin(), vRight.end());
     int iMin = INT_MAX;
     auto it = vLeft.begin();
     auto ij = vRight.rbegin();
     while ((it != vLeft.end()) && (ij != vRight.rend()))
     {
       const int tmp = *it + *ij;
       iMin = min(iMin, abs(tmp - goal));
       if (tmp > goal)
       {
         ij++;
       }
       else
       {
         it++;
       }
     }
     return iMin;
   }
 };