Readme

2035.Partition-Array-Into-Two-Arrays-to-Minimize-Sum-Difference

本题的思路来自于1755.Closest-Subsequence-Sum

本题要将最多30个数平均分成两组。这个规模暗示我们其实并没有贪心或者高效的算法，本题是指数级别的暴力搜索NPC问题。但是从30个里面遍历15个数的组合，是一个非常大的数字，这是无法暴力完成。怎么办呢？

我们发现如果只考虑一半的规模即n=15时，2^15=32768是一个可以接受的规模。这就提醒我们类似的1755，将数组分成两部分来处理。对于前半部分数组，我们可以遍历所有的组合（每个组合代表选取哪些元素），将每个组合的sum记录下来。假设前半部分的某个组合有i个元素，该组合的元素之和是x，那么我们自然希望在后半部分数组里挑选n-j个元素（记该组合的元素之和是y）使得x+y尽量接近sum-(x+y)。稍微变化一下，就知道我们需要找这样一个y，使得y尽量接近sum/2-x.

所以看出来，我们需要对后半部分数组进行预处理，构造一个Hash表，令Map[j]表示在后半部分数组里取j个元素的组合时，元素之和可能是哪些。对于前述的任何一个i和x，我们对应直接在Map[j]里面找最接近sum/2-x的数值（记做y）。那么|x+y-(sum-x-y)|就是一个可能的最优解。

所以总的时间复杂度是：1. 预处理部分，需要O(2^n*n)，其中乘以n表示遍历该state的每一个bit来计算sum。2. 遍历左边部分的所有组合（对应的i和x），然后在右边的Map[n-j]里面用二分来挑选最接近的数值，故是o(2^n*log(2^n)) = o(2^n*n)