最接近目标值的子序列和

给你一个整数数组 nums 和一个目标值 goal 。

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

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

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

**提示：
1 <= nums.length <= 40
-107 <= nums[i] <= 107
-10^9^ <= goal <= 10^9^**

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/closest-subsequence-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、解题思路

看题目数据范围,goal在[-10^9^,10^9^]如果背包搞二维表超时了背包动态规划不能用但是数组个数少,用分治

左部分,右部分每个数要跟不要全部展开,2^20^,百万级别

最接近目标的
有可能是只用左侧的这20个数搞出来的
也有可能是只用右侧的这20个数搞出来的
或者左侧给我一个累加和我看看右侧选哪个累加和加完之后离它最近。
你把左侧搞出来了,最多100万个累加和右侧最多搞定了100万个的累加和
左侧的所有累加和你都去找右侧哪个跟它加完之后最接近
这个过程不就是相当于100万乘以log100万这样一个复杂度吗?因为你把所有的累加和和加到有序表里去了

二、代码

    public static int[] l = new int[1 << 20];
    public static int[] r = new int[1 << 20];

    public static int minAbsDifference(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int le = process(nums, 0, nums.length >> 1, 0, 0, l);
        int re = process(nums, nums.length >> 1, nums.length, 0, 0, r);
        Arrays.sort(l, 0, le);
        Arrays.sort(r, 0, re--);
        int ans = Math.abs(goal);
        for (int i = 0; i < le; i++) {
            int rest = goal - l[i];
            while (re > 0 && Math.abs(rest - r[re - 1]) <= Math.abs(rest - r[re])) {
                re--;
            }
            ans = Math.min(ans, Math.abs(rest - r[re]));
        }
        return ans;
    }

    public static int process(int[] nums, int index, int end, int sum, int fill, int[] arr) {
        if (index == end) {
            arr[fill++] = sum;
        } else {
            fill = process(nums, index + 1, end, sum, fill, arr);
            fill = process(nums, index + 1, end, sum + nums[index], fill, arr);
        }
        return fill;
    }

总结

在做题的时候,我们需要分析题目的数据量,根据数据量来猜解法
例如这一题中,我们可以使用分治的思想