You are given an integer array nums
of 2 * n
integers. You need to partition nums
into two arrays of length n
to minimize the absolute difference of the sums of the arrays. To partition nums
, put each element of nums
into one of the two arrays.
Return the minimum possible absolute difference.
Example 1:
nums = [3,9,7,3]
Output: 2
Explanation: One optimal partition is: [3,9]
and [7,3]
. The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2
.
Example 2:
nums = [-36,36]
Output: 72
Explanation: One optimal partition is: [-36]
and [36]
. The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72
.
Example 3:
nums = [2,-1,0,4,-2,-9]
Output: 0
Explanation: One optimal partition is: [2,4,-9]
and [-1,0,-2]
. The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0
.
Describe an algorithm to solve this problem efficiently. What is the time and space complexity of your solution? Can you provide the code?
The most straightforward approach is to generate all possible partitions of the nums
array into two subarrays of size n
. For each partition, calculate the absolute difference between the sums of the two subarrays, and keep track of the minimum difference found so far.
This can be implemented using recursion or bit manipulation to generate all possible subsets. Each element can either belong to the first or the second subarray.
Code (Python):
import itertools
def min_abs_difference_brute_force(nums):
n = len(nums) // 2
min_diff = float('inf')
for i in range(1 << (2 * n)):
group1 = []
group2 = []
for j in range(2 * n):
if (i >> j) & 1:
group1.append(nums[j])
else:
group2.append(nums[j])
if len(group1) == n:
min_diff = min(min_diff, abs(sum(group1) - sum(group2)))
return min_diff
Time Complexity: O(22n * n), where n is half the length of the input array. We iterate through all 22n possible subsets and calculate the sum of each subset, taking O(n) time.
Space Complexity: O(n) to store the two subarrays.
Since the constraint 1 <= n <= 15
, a brute-force approach will have a time complexity of 2^30 in the worst case. To optimize, we can use the meet-in-the-middle technique.
nums
array into two halves, each of size n
. Let's call them left
and right
.k
(0 to n), store all subset sums of size k
for both left
and right
in separate lists.k
from 0 to n
.
k
, iterate through all possible subset sums sum_left
in the left
list of size k
.sum_right
in the right
list of size n - k
such that sum_left + sum_right
is as close as possible to total_sum / 2
. Use binary search to find the closest sum_right
.Code (Python):
import bisect
def min_abs_difference(nums):
n = len(nums) // 2
total_sum = sum(nums)
def subset_sums(arr):
sums = [[] for _ in range(n + 1)]
for mask in range(1 << n):
count = 0
subset_sum = 0
for i in range(n):
if (mask >> i) & 1:
subset_sum += arr[i]
count += 1
sums[count].append(subset_sum)
for i in range(n + 1):
sums[i].sort()
return sums
left = nums[:n]
right = nums[n:]
left_sums = subset_sums(left)
right_sums = subset_sums(right)
min_diff = float('inf')
for k in range(n + 1):
for sum_left in left_sums[k]:
remaining_sum = total_sum // 2 - sum_left
right_arr = right_sums[n - k]
idx = bisect.bisect_left(right_arr, remaining_sum)
if idx < len(right_arr):
min_diff = min(min_diff, abs(total_sum - 2 * (sum_left + right_arr[idx])))
if idx > 0:
min_diff = min(min_diff, abs(total_sum - 2 * (sum_left + right_arr[idx - 1])))
return min_diff
Time Complexity: O(n * 2n + n2 * log(2n)). Generating subsets takes O(n * 2n). Sorting the subset sums takes O(2nlog(2n)) which becomes O(n*2n). The binary search part takes O(n2*log(2n))
Space Complexity: O(n * 2n) to store the subset sums for both halves.
1 <= n <= 15
and nums.length == 2 * n
. Thus, empty input will never occur.n
such numbers could be as large as 15 * 10^7 = 1.5 * 10^8
. This is within the range of int
in Python, and will not overflow.