最接近目标值的子序列和。给你一个整数数组 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
本题数据量描述:
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
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
}
}执行结果如下：
