将数组分成两个数组并最小化数组和的差

难度: Hard

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回最小的数组和之差。

示例 1：

example-1

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：

输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。

示例 3：

example-3

输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

提示：

1 <= n <= 15
nums.length == 2 * n
-10⁷ <= nums[i] <= 10⁷

Submission

运行时间: 1060 ms

内存: 0.0 MB

# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n = len(nums)//2
#         dp0, dp2 = set([0]), set()
#         for i in range(n):
#             ndp0, ndp2 = set(), set()
#             nd0, nd2 = abs(nums[2*i]-nums[2*i+1]), nums[2*i]+nums[2*i+1]
#             for d in dp0:
#                 ndp0.update([d+nd0, abs(d-nd0)])
#                 ndp2.update([nd2+d, nd2-d])
#             for d in dp2:
#                 ndp0.add(abs(nd2-d))
#                 ndp2.update([d+nd0, d-nd0])
#             dp0, dp2 = ndp0, ndp2
#         return min(dp0)

# # past 134/201
# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n = len(nums)//2
#         dp = defaultdict(set)
#         dp[0] = set([0])
#         for i in range(n):
#             nd0, nd2 = abs(nums[2*i]-nums[2*i+1]), nums[2*i]+nums[2*i+1]
#             ndp = defaultdict(set)
#             for dn, dss in dp.items():
#                 mdn = 2*min(i+1, n-(i+1))
#                 for ds in dss:
#                     if dn==0: ndp[dn].update([abs(ds+nd0), abs(ds-nd0)])
#                     elif dn<=mdn: ndp[dn].update([ds+nd0, ds-nd0])
#                     if 0<=dn-2<=mdn: ndp[dn-2].add(abs(ds-nd2) if dn==2 else ds-nd2)
#                     if dn+2<=mdn:
#                         ndp[dn+2].add(ds+nd2)
#                         if dn==0: ndp[dn+2].add(nd2-ds)
#             dp = ndp
#         return min(dp[0])

# # past 134/201
# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n = len(nums)//2
#         dp = defaultdict(set)
#         dp[0] = set([0])
#         for i in range(2*n):
#             ndp = defaultdict(set)
#             for dn, dss in dp.items():
#                 for ds in dss:
#                     if dn>=1:
#                         ndp[dn-1].add(abs(ds-nums[i]) if dn==1 else ds-nums[i])
#                     if dn+1<=min(i+1, 2*n-(i+1)): 
#                         ndp[dn+1].add(ds+nums[i])
#                         if dn==0: ndp[dn+1].add(nums[i]-ds)
#             dp = ndp
#         return min(dp[0])



# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n = len(nums)//2
#         dp = {0: [[0, 0], [0, 0]]}
#         def _update_n1(dn, pm, nm, nu):
#             pbit, mp = pm
#             nbit, mn = nm
#             npbit, nmp = 0, mp
#             nnbit, nmn = 0, mn
#             for i in range(mp):
#                 if pbit&(1<<i)==0: continue
#                 nds = i-nu
#                 if dn==1 or nds>=0: 
#                     npbit |= 1<<abs(nds)
#                     nmp = max(nmp, abs(nds))
#                 else:
#                     nnbit |= 1<<abs(nds)
#                     nmn = max(nmn, abs(nds))
#             for i in range(mn):
#                 if nbit&(1<<i)==0: continue
#                 nds = -i-nu
#                 if dn==1 or nds>=0: 
#                     npbit |= 1<<abs(nds)
#                     nmp = max(nmp, abs(nds))
#                 else:
#                     nnbit |= 1<<abs(nds)
#                     nmn = max(nmn, abs(nds))
#             return [npbit, nmp], [nnbit, nmn]

# #                     if dn+1<=min(i+1, 2*n-(i+1)): 
# #                         ndp[dn+1].add(ds+nums[i])
# #                         if dn==0: ndp[dn+1].add(nums[i]-ds)

#         def _update_p1(dn, pm, nm, nu):
#             pbit, mp = pm
#             nbit, mn = nm
#             npbit, nmp = 0, mp
#             nnbit, nmn = 0, mn
#             for i in range(mp):
#                 if pbit&(1<<i)==0: continue
#                 nds = i+nu
#                 if nds>=0:
#                     npbit |= 1<<abs(nds)
#                     nmp = max(nmp, abs(nds))
#                 else:
#                     nnbit |= 1<<abs(nds)
#                     nmn = max(nmn, abs(nds))
#                 if dn==0:
#                     nds = nu-i


#             for i in range(mn):
#                 if nbit&(1<<i)==0: continue

#         for i in range(2*n):
#             ndp = {}
#             for dn, bits in dp.items():
#                 pm, nm = bits



#                 if dn>=1:
#                     pm, nm = ndp.get(dn-1, [0, 0])
#                     if dn==1: pm |= 1<<abs(ds-nums[i])
#                     else:
#                         pm, nm = _update(ds-nums[i], pm, nm)
#                     ndp[dn-1] = [pm, nm]
#                 if dn+1<=min(i+1, 2*n-(i+1)): 
#                     pm, nm = ndp.get(dn+1, [0, 0])
#                     pm, nm = _update(ds+nums[i], pm, nm)
#                     if dn==0: pm, nm = _update(nums[i]-ds, pm, nm)
#                     ndp[dn+1] = [pm, nm]
#             dp = ndp
#         md = 0
#         while dp[0][0]%2==0:
#             md += 1
#             dp[0][0] //= 2
#         return md

# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n, ss = len(nums)//2, sum(nums)
#         ts = ss//2
#         dp = [[ts, ts+1] for _ in range(n+1)]
#         for l in range(1, 2*n+1):
#             for k in range(1, min(l, n)+1):
#                 ns0, ns1 = dp[k-1][0]+nums[l-1], dp[k-1][1]+nums[l-1]
#                 if dp[k][0]<ns0<=ts: dp[k][0] = ns0
#                 if dp[k][1]<ns0<=ts+1: dp[k][1] = ns1
#         return min(abs(ss-2*dp[-1][0]), abs(ss-2*dp[-1][1]))

# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n, ss = len(nums)//2, sum(nums)
#         dp = [ss for _ in range(n+1)]
#         for l in range(1, 2*n+1):
#             for k in range(1, min(l+n)+1):
#                 dp[k] = min(dp[k], abs(ss-2*(dp[k-1]+nums[l-1])))
#         return dp[-1]


# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n, ts = len(nums)//2, sum(nums)
#         lns, rns = nums[:n], nums[n:]
#         def _subset_sum(arr):
#             dp = defaultdict(set)
#             dp[0] = set([0])
#             for i in range(len(arr)):
#                 ndp = defaultdict(set)
#                 for c in range(i+1):
#                     ndp[c].update(dp[c])
#                     ndp[c+1] = set([s+arr[i] for s in dp[c]])
#                 dp = ndp
#             return dp

#         def _find_peak(a, barr):
#             # find the peak value of an array with unique numbers
#             nb = len(barr)
#             l, r = 0, nb-1
#             while l<r:
#                 m = (l+r)//2
#                 s0, s1 = abs(ts-2*(a+barr[m])), abs(ts-2*(a+barr[m+1]))
#                 if s0>s1: l = m+1
#                 else: r = m
#             return abs(ts-2*(a+barr[r]))

#         ldss, rdss = _subset_sum(lns), _subset_sum(rns)
#         md = sys.maxsize
#         for i in range(n+1):
#             lss, rss = ldss[i], rdss[n-i]
#             sss = lss if len(lss)<len(rss) else rss
#             bss = rss if len(lss)<len(rss) else lss
#             sss = sorted(sss)
#             for a in bss:
#                 md = min(md, _find_peak(a, sss))
#             del ldss[i], rdss[n-i]
#         return md

# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         n, ts = len(nums)//2, sum(nums)
#         lns, rns = nums[:n], nums[n:]
#         lts, rts = sum(lns), sum(rns)
#         def _subset_sum(arr):
#             nn, dp = len(arr), defaultdict(set)
#             dp[0] = set([0])
#             for i in range(nn):
#                 ndp = defaultdict(set)
#                 for c in range(min(i, nn//2)+1):
#                     ndp[c].update(dp[c])
#                     ndp[c+1] = set([s+arr[i] for s in dp[c]])
#                 dp = ndp
#             return dp

#         def _find_peak(a, barr, bts):
#             # find the peak value of an array with unique numbers
#             nb = len(barr)
#             l, r = 0, nb-1
#             while l<r:
#                 m = (l+r)//2
#                 s0, s1 = abs(ts-2*(a+bts-barr[m])), abs(ts-2*(a+bts-barr[m+1]))
#                 if s0>s1: l = m+1
#                 else: r = m
#             return abs(ts-2*(a+bts-barr[r]))

#         ldss, rdss = _subset_sum(lns), _subset_sum(rns)
#         md = abs(lts-rts)
#         for i in range(n//2+1):
#             lss, rss = ldss[i], rdss[i]
#             if len(lss)<len(rss):
#                 sss, bss, sts = sorted(lss), rss, lts
#             else:
#                 sss, bss, sts = sorted(rss), lss, rts
#             for a in bss:
#                 md = min(md, _find_peak(a, sss, sts))
#             del ldss[i], rdss[i]
#         return md

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n, ts = len(nums)//2, sum(nums)
        lns, rns = nums[:n], nums[n:]
        lts, rts = sum(lns), sum(rns)
        def _subset_sum(arr):
            nn, dp = len(arr), defaultdict(set)
            dp[0] = set([0])
            for i in range(nn):
                ndp = defaultdict(set)
                for c in range(min(i, nn//2)+1):
                    ndp[c].update(dp[c])
                    ndp[c+1] = set([s+arr[i] for s in dp[c]])
                dp = ndp
            return dp

        ldss, rdss = _subset_sum(lns), _subset_sum(rns)
        md = abs(lts-rts)
        for i in range(n//2+1):
            lss, rss = ldss[i], rdss[i]
            if len(lss)<len(rss): sss, bss, sts = sorted(lss), rss, lts
            else: sss, bss, sts = sorted(rss), lss, rts
            for a in bss:
                targ_rs = sts - (ts/2 - a)
                bti = bisect_right(sss, targ_rs)
                for j in [bti-1, bti]:
                    if j>=len(sss): continue
                    md = min(md, abs(ts-2*(a+sts-sss[j])))
            del ldss[i], rdss[i]
        return md


# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         N = len(nums) // 2 # Note this is N/2, ie no. of elements required in each.
        
#         def get_sums(nums): # generate all combinations sum of k elements
#             ans = {}
#             N = len(nums)
#             for k in range(1, N+1): # takes k element for nums
#                 sums = []
#                 for comb in combinations(nums, k):
#                     s = sum(comb)
#                     sums.append(s)
#                 ans[k] = sums
#             return ans
        
#         left_part, right_part = nums[:N], nums[N:]
#         left_sums, right_sums = get_sums(left_part), get_sums(right_part)
#         ans = abs(sum(left_part) - sum(right_part)) # the case when taking all N from left_part for left_ans, and vice versa
#         total = sum(nums) 
#         half = total // 2 # the best sum required for each, we have to find sum nearest to this
#         for k in range(1, N):
#             left = left_sums[k] # if taking k no. from left_sums
#             right = right_sums[N-k] # then we have to take remaining N-k from right_sums.
#             right.sort() # sorting, so that we can binary search the required value
#             for x in left:
#                 r = half - x # required, how much we need to add in x to bring it closer to half.
#                 p = bisect.bisect_left(right, r) # we are finding index of value closest to r, present in right, using binary search
#                 for q in [p, p-1]:
#                     if 0 <= q < len(right):
#                         left_ans_sum = x + right[q]
#                         right_ans_sum = total - left_ans_sum
#                         diff = abs(left_ans_sum - right_ans_sum)
#                         ans = min(ans, diff) 
#         return ans

Explain

这个题解的思路是将数组分成左右两部分,分别求出左右两部分所有可能的子集和。然后对于左边每一个可能的子集和,在右边部分通过二分查找找到最接近总和一半的子集和,两者相加即可得到最接近总和一半的一种划分方式。所有划分方式中的最小值即为答案。

时间复杂度: O(n*2^n)

空间复杂度: O(2^n)

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n, ts = len(nums)//2, sum(nums)
        lns, rns = nums[:n], nums[n:]
        lts, rts = sum(lns), sum(rns)
        # 求一个数组的所有子集和
        def _subset_sum(arr):
            nn, dp = len(arr), defaultdict(set)
            dp[0] = set([0]) 
            for i in range(nn):
                ndp = defaultdict(set)
                for c in range(min(i, nn//2)+1):
                    ndp[c].update(dp[c])
                    ndp[c+1] = set([s+arr[i] for s in dp[c]])
                dp = ndp
            return dp
        
        ldss, rdss = _subset_sum(lns), _subset_sum(rns) 
        md = abs(lts-rts) 
        for i in range(n//2+1):
            lss, rss = ldss[i], rdss[i]
            if len(lss)<len(rss): sss, bss, sts = sorted(lss), rss, lts
            else: sss, bss, sts = sorted(rss), lss, rts
            for a in bss: 
                targ_rs = sts - (ts/2 - a)
                bti = bisect_right(sss, targ_rs) 
                for j in [bti-1, bti]:
                    if j>=len(sss): continue
                    md = min(md, abs(ts-2*(a+sts-sss[j])))
            del ldss[i], rdss[i]
        return md

Explore

将数组平分为两部分来计算子集和是基于计算复杂度和实现的可行性的考虑。对于一个数组，其可能的子集数量是指数级增长的，即对于n个元素的数组，子集数为2^n。如果按照不平均分割，比如一大一小两部分，小部分虽然子集计算快但其组合的灵活性低，而大部分的子集计算则非常耗时且难以处理。平分数组可以较好地平衡这两部分的计算量，且每部分处理的子集数目相对平衡，这对后续的操作如比较和二分查找也更为有利。

默认字典（defaultdict）在Python中相比普通字典的优势在于它提供了一个默认值，这使得当访问一个不存在的键时，不会抛出错误而是返回一个默认值。在处理子集和时，使用默认字典可以自动地为新的子集和分类初始化一个空集合，避免了额外的键存在检查和初始化代码，从而简化代码的复杂性并提高效率。

在处理子集和时对每个集合的元素数量进行限制主要是为了减少不必要的计算和存储。因为题目的目的是找出最小的差值，而这通常不需要考虑所有可能的子集组合，尤其是那些元素过多或过少的子集，它们对平衡总和的贡献较小。通过限制元素数量可以有效地减少处理的子集数量，从而提高算法的效率并减少内存使用。

在题解中，通过二分查找的应用旨在快速定位到与目标值（总和的一半）最接近的子集和。具体做法是先将其中一个部分的子集和排序，然后对于另一部分的每个子集和，计算出与总和一半相对应的目标子集和，使用二分查找在已排序的子集和中查找最接近这个目标的值。通过查找最接近的两个点（bisect_right返回的位置和前一个位置），可以比较哪个子集和与目标更接近，从而确保找到差值最小的组合。