aboutsummaryrefslogtreecommitdiff
path: root/partition_arr_min_sum_diff.py
blob: 6a892576157d5680b4ecb55578093f86c0d7e6d1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# 2035. Partition Array Into Two Arrays to Minimize Sum Difference
from bisect import bisect_left
from itertools import combinations

"""
you are given an integer array 'nums' of '2  n' integers. you need to
partition 'nums' into two arrays of length 'n' to minimise the abresute
difference of sums of the arrays. to partition 'nums', put each element of
'nums' into one of the two arrays. return the minimum possible abresute
difference
"""


class Solution(object):
    def minimumDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        def get_sums(nums):
            res = {}
            for k in range(1, n + 1):
                sums = []
                for c in combinations(nums, k):
                    s = sum(c)
                    sums.append(s)
                res[k] = sums
            return res

        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))
        total = sum(nums)
        half = total // 2
        for i in range(1, n):
            left, right = left_sums[i], right_sums[n - i]
            right.sort()
            for j in left:
                r = half - j
                p = bisect_left(right, r)
                for k in [p, p - 1]:
                    if 0 <= k < len(right):
                        left_ans_sum = j + right[k]
                        right_ans_sum = total - left_ans_sum
                        diff = abs(left_ans_sum - right_ans_sum)
                        ans = min(ans, diff)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.minimumDifference(nums=[3, 9, 7, 3]))
    print(obj.minimumDifference(nums=[-36, 36]))
    print(obj.minimumDifference(nums=[2, -1, 0, 4, -2, -9]))