本题的标签是Divide and Conquer和Meet in the Middle，前者还好说，但是后者听起来就不像个算法，甚至从我个人角度来讲，这两个可以统称为Divide and Conquer（分治法）。毕竟分治法，也可以简单的分成两份嘛，不用分那么复杂。
注意：文章中一切注解皆为Python代码
题目非常简单。给定一个包含正负数字的列表，在所有可能的序列(sequence)中，选出一个序列，使得序列之和与给定数字(goal)的差的绝对值最小；也就是
1 min([abs(sum(s) - goal) for s in sequences])
最终返回这个值。
很明显，暴力解法就是找出所有可能形成的序列组合，求和后比较差值，这个方法的时间复杂度为O(2^N)，即长度为N的列表中，每个数字可以有两种选择（包含或者不包含），因此O(2^N)。
过程非常简单，用set找出所有的不重复的数列和，逐个跟goal做减法求绝对值。
1 class Solution:
2 def minAbsDifference(self, nums: List[int], goal: int) -> int:
3 def sums(arr):
5 sumset = {0}
6 for a in arr:
7 sumset |= set(a+x for x in sumset)
8 return sumset
9 return min(abs(seq-goal) for seq in sums(nums))
那我们现在来想一下，给定时间复杂度是O(2^N)，有什么方式可以大幅降低时间复杂度呢？
如果能把原数列一分为二，分别求的话即O(2^(N/2)) * 2，那么有没有什么方法可以对这个级别的时间复杂度进行一些操作，得出最终的结果呢。
显然是有的！做过LeetCode 1099. Two Sum Less Than K吗？既然我们有两份包含数字和的集合，为什么不用一个类似的方法来实现呢？
现在我们来逆向思考一下，给定x, y, goal，如何让abs(x+y-goal)最小呢？答案显而易见，就是让abs(x+y-goal)尽可能的贴近0；也就是x+y-goal = 0，或者x = goal - y说到这里是不是有什么启发呢？重点来了：
如果我们将两个集合中的一个转化为列表，并且排序（这里叫做列表s1）
之后，对于另一个集合中的每一个的值y，在s1上进行二分搜索，搜索的目标为goal-y
每一个循环进行一次二分搜索，和最小绝对值差的运算
最终得出结果
过程看完了，时间复杂度是怎么样的呢？以下这里直接忽略常数，集合长度设为M = 2 ^ (N/2)
集合转列表O(M)，排序列表O(MlogM)，
二分搜索一次O(logM)，二分搜索M次则是O(MlogM)
再加上之前创造两个集合O(2^(N/2))
因此，总时间复杂度为O(2^(N/2)) + O(MlogM) = O( 2^(N/2) + 2 ^ (N/2)*log(2 ^ (N/2)) )。题目给定的输入范围是
1 <= nums.length <= 40
如果，带入N=40计算暴力解复杂度和优化后的复杂度的话，会得到：
暴力解：O(2 ^ N) = 2 ^ 40
优化解：O(2^(N/2) + 2 ^ (N/2)*log(2 ^ (N/2)) ) ~= 2 ^ 24
性能表现提高了2^16 = 65536倍，代码如下：
1 class Solution:
2 def minAbsDifference(self, nums: List[int], goal: int) -> int:
3 def sums(arr):
4 sumset = {0}
5 for a in arr:
6 sumset |= set(a+x for x in sumset)
7 return sumset
8 s2 = sums(nums[1::2]) # 分治，把数列按奇偶索引一分为二
9 s1 = sorted(sums(nums[::2]))
10 m = len(s1)
11 ans = sys.maxsize
12 for val in s2:
13 = bisect.bisect_left(s1, goal-val) # 二分法
14 i0 <= i < m:
15 ans = min(ans, abs(s1[i] + val - goal))
16 if 0 <= i-1 < m:
17 ans = min(ans, abs(s1[i-1] + val - goal))
18 return ans
既然我们可以把数列一分为二以降低时间复杂度，那么为什么不把它一分为3，4份呢？原因很简单，没有二分法的支持，无论分多少份都是徒劳的，二分法O(logN)的时间复杂度真的是一份催化剂。因此我们可以说，将数列一分为二是大大降低时间复杂度的上限，二分法是在这一基础上完成题目要求的核心解法。
之后我们再看到需要O(2^N)复杂度的算法时，不妨想一想利用排序+二分法是否可以大大的做到效率加成。
LeetCode 1755. Closest Subsequence Sum (时间复杂度为2^N时的数学优化）
原文：https://www.cnblogs.com/cjyangblog/p/14651226.html