yhtest

这里整理一下 [ 在数组中选取子集，达到某一目标 ] 这类问题的通用解法。

类型1 : 目标值明确，可以把目标值看出背包容量，数组值看做物品，转成背包问题
类型2 : 目标值不明确，容量不知道，不能用背包，只能枚举子集的和
本题
1755.最接近目标值的子序列和
题意:目标值t, 子序列和sum, 求min = abs(sum - target)的最小值。
目标值不明确，背包容量不确定，不能转为背包问题，只能二分拆数组，来降低复杂度，然后枚举子数组的子集的和，最后用双指针指向两个子集和的元素，不断逼近目标值。
有人看到这里可能觉得是不是写错了，这题题目已经给出了目标值，为什么还说是目标值不明确的呢？
原因在于，题目给的target不是我们最后要组合的目标值，题目要我们求的是min的最小值，这里的最小值我们在解题之前是不知道的。

class Solution {
public:
    int minAbsDifference(vector& nums, int goal) {
        int n = nums.size();
        int half = n / 2;
        int ls = half, rs = n - half;
        
        vector lsum(1 << ls, 0);
        for (int i = 1; i < (1 << ls); i++) {
            for (int j = 0; j < ls; j++) {
                if ((i & (1 << j)) == 0) continue;
                lsum[i] = lsum[i-(1<                 break;
            }
        }
        vector rsum(1 << rs, 0);
        for (int i = 1; i < (1 << rs); i++) {
            for (int j = 0; j < rs; j++) {
                if ((i & (1 << j)) == 0) continue;
                rsum[i] = rsum[i-(1<                 break;
            }
        }
        sort(lsum.begin(), lsum.end());
        sort(rsum.begin(), rsum.end());
        
        int ret = INT_MAX;
        for (int x: lsum) {
            ret = min(ret, abs(goal - x));
        }
        for (int x: rsum) {
            ret = min(ret, abs(goal - x));
        }
        
        int i = 0, j = rsum.size() - 1;
        while (i < lsum.size() && j >= 0) {
            int s = lsum[i] + rsum[j];
            ret = min(ret, abs(goal - s));
            if (s > goal) {
                j--;
            } else {
                i++;
            }
        }
        return ret;
    }
};