lc1755 最接近目标值的子序列和

给你一个整数数组nums和一个目标值goal，需要从nums中选出一个子序列，使子序列元素总和最接近goal，返回abs(sum-goal)可能的最小值。数组的子序列指通过移除原数组中的某些元素（可能全部或无）而形成的数组。
1<=nums.length<=40; -1e7<=nums[i]<=1e7; -1e9<=goal<=1e9

值域过大，不能用背包求，而直接dfs时间复杂度为O(2^40)，会TLE，考虑双向dfs，然后凑答案，时间复杂度为O(2*2^20)。

class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        set<int> st1, st2;
        
        auto dfs = [&](auto self, int x, int R, int cur, set<int> &st) -> void {
            if (x == R) {
                st.insert(cur);
                return;
            }
            self(self, x+1, R, cur, st);
            self(self, x+1, R, cur+nums[x], st);
        };
        
        dfs(dfs, 0, n/2, 0, st1);
        dfs(dfs, n/2, n, 0, st2);
        int ans = INT_MAX;
        for (auto i : st1) {
            auto it = st2.lower_bound(goal-i);
            if (it != st2.end()) {
                ans = min(ans, abs(i + *it - goal));
            }
            if (it != st2.begin()) {
                --it;
                ans = min(ans, abs(i + *it - goal));
            }
        }
        return ans;
    }
};