Problem statement

https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/

Solution

The idea is to split data into two halves of length n, then we can have options:

  1. Take 0 elements from the first part and n from the second.
  2. Take 1 elements from the first part and n-1 from the second. …

Also notice that we want parts to be as close to each other as possible and this means that we are looking for n numbers with sum closest to sum(nums)//2.

  1. We can use dfs to generate all sums of subsets: sums[i] will keep all sums of i elements. We do it for both halves.
  2. We use two pointers approach to find the sum closes to target, it is in fact very similar to 2sum closest problem.

Complexity

It is O(2^n * n) for time and O(2^n) for space.

Code

class Solution:
    def minimumDifference(self, nums):
        def dfs(i, taken, sm, sums, arr):
            if i == len(arr): return
            sums[taken].add(sm)
            dfs(i+1, taken+1, sm+arr[i], sums, arr)
            dfs(i+1, taken, sm, sums, arr)
        
        sums1, sums2 = defaultdict(set), defaultdict(set)
        n, target = len(nums)//2, sum(nums)
        dfs(-1, 0, 0, sums1, nums[:n])
        dfs(-1, 0, 0, sums2, nums[n:])
        
        ans = float("inf")
        
        for i in range(n + 1):
            t1 = sorted(sums1[i])
            t2 = sorted(sums2[n - i])
            
            beg, end = 0, len(t2) - 1

            while beg < len(t1) and end >= 0:
                sm = t1[beg] + t2[end]
                ans = min(ans, abs(2*sm - target))
        
                if 2*sm <= target:
                    beg += 1
                else:
                    end -= 1
            
        return ans