LC-2035 Hard LeetCode

2035. Partition Array Into Two Arrays to Minimize Sum Difference

Array Two Pointers Binary Search Dynamic Programming Bit Manipulation Ordered Set Bitmask

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 22% Topics: Array, Two Pointers, Binary Search, Dynamic Programming, Bit Manipulation, Ordered Set, Bitmask

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(2^n)

import itertools
import bisect


class Solution(object):
    def minimumDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = nums[:len(nums)//2], nums[len(nums)//2:]
        total1, total2 = sum(left), sum(right)
        result = float("inf")
        for k in xrange(len(left)+1): 
            sums = sorted(2*sum(comb)-total1 for comb in itertools.combinations(left, k))
            for comb in itertools.combinations(right, len(left)-k): 
                diff = 2*sum(comb)-total2
                i = bisect.bisect_left(sums, -diff)
                if i < len(sums):
                    result = min(result, abs(sums[i]+diff))
                if i > 0:
                    result = min(result, abs(sums[i-1]+diff))
        return result

Solution from kamyu104/LeetCode-Solutions · MIT