golang 解法, 执行用时: 624 ms, 内存消耗: 6.9 MB, 提交时间: 2023-08-16 17:31:43

func minimumDifference(nums []int) int {
	n := len(nums) / 2
	a := nums[:n]
	res := make([][]int, n+1)
	for i := 0; i < 1<<n; i++ {
		sum, cnt := 0, 0
		for j, v := range a {
			if i>>j&1 > 0 { // 1 视作取正
				sum += v
				cnt++
			} else { // 0 视作取负
				sum -= v
			}
		}
		res[cnt] = append(res[cnt], sum) // 按照取正的个数将元素和分组
	}

	for _, b := range res {
		sort.Ints(b) // 排序，方便下面二分
	}

	ans := math.MaxInt64
	a = nums[n:]
	for i := 0; i < 1<<n; i++ {
		sum, cnt := 0, 0
		for j, v := range a {
			if i>>j&1 > 0 {
				sum += v
				cnt++
			} else {
				sum -= v
			}
		}
		// 在对应的组里二分最近的数
		b := res[cnt]
		j := sort.SearchInts(b, sum)
		if j < len(b) {
			ans = min(ans, b[j]-sum)
		}
		if j > 0 {
			ans = min(ans, sum-b[j-1])
		}
	}
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

python3 解法, 执行用时: 2380 ms, 内存消耗: 19 MB, 提交时间: 2023-08-16 17:30:03

'''
折半枚举+排序+二分
两个数组和之差可以视作从 nums 中选 n 个数取正号，其余 n 个数取负号，然后求元素和。
我们可以使用折半枚举的方法，枚举 nums 的前 n 个元素取正或取负的所有情况，
按取正的个数分组，并按照元素和排序。然后枚举 nums 的后 n 个元素取正或取负的所有情况，
然后去对应的组里二分找元素和最近的数，答案即为所有情况中最小的差值。
'''

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 2
        left = [[] for _ in range(n+1)]
        right = [[] for _ in range(n+1)]
        
        def dfs(nums, res, i, c, record):
            if i == n:
                #bisect.insort(record[c],res)  这个太慢了，后排序更快一点
                record[c].append(res)
                return 
            dfs(nums, res+nums[i],i+1,c+1,record)
            dfs(nums,res-nums[i],i+1,c,record) 
        
        dfs(nums[:n],0,0,0, left)
        dfs(nums[n:],0,0,0, right)
            
        ret = inf
        for i in range(n+1):
            lvs = left[i]
            rvs = right[i]
            lvs.sort()
            rvs.sort()
            lvs.append(inf)
            rvs.append(inf)
            k,j = 0,0 
            while k < len(lvs) and j < len(rvs) :
                t  = lvs[k] - rvs[j]
                if abs(t) < ret:      
                   ret = abs(t)
                if t == 0:
                    return 0
                if t < 0:
                    k += 1 
                else:
                    j += 1
        return ret