折半搜索（meet-in-the-middle）：
将整个搜索的过程分为两部分:
然后每部分分别进行搜索，最后将得到两个答案序列，再将答案序列进行合并，即可得到最终的答案。

搜索的时间复杂度往往是指数级别的
比如，在每一层搜索时，假如都有两种选择，那么其时间复杂度为 O(${2^n}$)
当 n 较大时，往往会导致超时。
此时，如果使用折半搜索:其时间复杂度将缩小为 O(${2^\frac{n}{2}}$ + 合并操作的时间复杂度)

折半搜索 + 二分

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

题目描述：
给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，
如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

数据范围：
1 <= nums.length <= 40
${-10^7}$ <= nums[i] <= ${10^7}$
${-10^9}$ <= goal <= ${10^9}$

思路：
（1）第一次搜索：我们枚举前半段数组的所有元素选或不选得到所有状态的子序列和 sum，
     然后将每个 sum 存入数组 q，并对数组 q 进行排序。

（2）第二次搜索：尝试从后半段数组中选一些元素，找到后半段一个可行解 sum 后，
     然后我们二分查找数组 q，即从前半段中选一个子序列的和，
     然后二分找到小于等于 goal 的最大位置（sum+q[mid]<=goal mid的最大位置）。

（3）当然我们要更新 res 的话，还要比较大于 goal 的最小位置，即最接近 goal 的位置，位于它的两侧。

友情提醒：如果不愿意手写二分的话（反正我是不愿意）：(从小到大排序)
可以用upper_bound()找到大于 goal-sum 的一个位置,然后再比较它前面的一个位置（如果有的话）。

const int N = 2e6+10;
class Solution {
    //2^20 < 2 * 1000 * 10000
    using LL = long long;
    LL q[N];
    int goal;
    int k;
    LL res;
    int cnt;
    int n;
    void dfs1(vector<int> &nums,int u,LL sum){
        if(u>=k) {
            q[cnt++] = sum;
            return;
        }
        dfs1(nums,u+1,sum); //不选
        dfs1(nums,u+1,sum+nums[u]);//选
    }

    void dfs2(vector<int> &nums,int u,LL sum){
        if(u>=n){
            auto idx = upper_bound(q,q+cnt,goal-sum)-q;
            //判断有没有越界,没有越界更新
            if(idx<cnt) res = min(res,abs(goal-sum-q[idx]));
            //继续比较它前面一个元素：因为最近的两个都可能是ans
            idx--;
            if(idx>=0) res = min(res,abs(goal-sum-q[idx]));

            return;
        }
        dfs2(nums,u+1,sum); //不选
        dfs2(nums,u+1,sum+nums[u]);//选
    }

public:
    int minAbsDifference(vector<int>& nums, int _goal) {
        goal = _goal;
        n = nums.size();
        k = n/2;
        sort(nums.rbegin(),nums.rend());
        //搜索前一半
        dfs1(nums,0,0);
        res = 0x3f3f3f3f;
        //排序q数组 为了二分:
        sort(q,q+cnt);
        //去重优化[要看题目具体情况能不能去重]
        cnt = unique(q,q+cnt)-q;
        //搜索后一半
        dfs2(nums,n/2,0);

        return res;
    }
};