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]))
|