Daily bit(e) of C++ | Partition array into two to minimize sum difference
Daily bit(e) of C++ #112, Common interview problem: Partition array into two to minimize sum difference
Today we will look at a common interview problem: Partition an array into two to minimize the sum difference.
Given an array of integers with n*2 elements, partition the array into two partitions of size n such that their sums are as close as possible (i.e. minimize the absolute difference between them). Return the best achievable sum distance.
Assume n < 16 and, for simplicity, that all sub-sums and distances fit in an int.
For example, in the above example, the two partitions {2,4,-9} and {-1,0,-2} sum up to -3, leading to the optimal zero distance.
Before you continue reading, I encourage you to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/9TY51KzEv.
Solution
Let’s first analyze what we are trying to do. We are trying to find the minimal partition. That is a partition into A and B, so abs(a_sum-b_sum) is minimal.
Because we are splitting the array into two equal parts, we can ignore the B partition and rewrite our target:
b_sum == total_sum - a_sum
abs(a_sum-b_sum) == abs(a_sum-(total_sum-a_sum)) == abs(total_sum - 2*a_sum)
Unfortunately, this is an NP problem, meaning our only choice is to go over all the combinations. For n < 16, that sounds feasible; however, what we are looking for is picking 16 elements from 32, which translates to roughly 6*10^8 combinations, which is feasible but would take a very long time (hours/days).
Since we are looking for a minimum, we know the optimal value of a_sum. We can therefore use the “Meet in the middle” technique.
If we split the array in the middle, partition A will have some elements in the left and some in the right sections. If we iterate over all possible combinations of elements in the left section (which is 2^n, i.e. 2^16 max), we can then look for the corresponding remainder (to reach the optimal a_sum) using binary search in the right section (which is log(2^n) == n, leaving us with O(2^n*n)).