2021-06-28：最接近目标值的子序列和。给你一个整数数组 nums 和一个目标值 goal 。你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。返回 abs(sum - goal) 可能的 最小值 。注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。输入：nums = [7,-9,15,-2], goal = -5。输出：1。解释：选出子序列 [7,-9,-2] ，元素和为 -4 。绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。

示例 1：

输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。
示例 2：

输入：nums = [7,-9,15,-2], goal = -5
输出：1
解释：选出子序列 [7,-9,-2] ，元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。
示例 3：

输入：nums = [1,2,3], goal = -7
输出：7

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

福大大 答案2021-06-28：

本题数据量描述:
1 <= nums.length <= 40，
-10^7 <= nums[i] <= 10^7，
-10^9 <= goal <= 10^9，
通过这个数据量描述可知，需要用到分治，因为数组长度不大，
而值很大，用动态规划的话，表会爆。
时间复杂度是O(2的20次方20)，空间复杂度是O(2的20次方2)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{1, 3, 5, 7, 9, 2, 4, 6, 8, 19}
    ret := minAbsDifference(arr, 11)
    fmt.Println(ret)
}

var l []int = make([]int, 1<<20)
var r []int = make([]int, 1<<20)

func minAbsDifference(nums []int, goal int) int {
    if len(nums) == 0 {
        return goal
    }
    le := process(nums, 0, len(nums)>>1, 0, 0, l)
    re := process(nums, len(nums)>>1, len(nums), 0, 0, r)
    sort.Ints(l[0 : le+1])
    sort.Ints(r[0 : re+1])
    re--
    ans := getAbs(goal)
    for i := 0; i < le; i++ {
        rest := goal - l[i]
        for re > 0 && getAbs(rest-r[re-1]) <= getAbs(rest-r[re]) {
            re--
        }
        ans = getMin(ans, getAbs(rest-r[re]))
    }
    return ans
}

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

func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}
func getAbs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

执行结果如下：
图片

左神java代码