Split into Equal-Sized Groups with Closest Sums
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given an array `nums` of length `2 * n`, divide all its entries into two groups containing exactly `n` entries each. The groups need not be contiguous, and every entry must belong to exactly one group. Return the smallest possible absolute difference between the two group sums. Values can be negative.
```cpp
class Solution {
public:
int minimumDifference(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [1,2,3,4]
Output: 0
Explanation: Groups [1,4] and [2,3] both sum to 5.
```
**Example 2:**
```text
nums = [-5,7]
Output: 12
Explanation: Each group must contain one entry, forcing sums -5 and 7.
```
### Constraints
- `1 <= n <= 15`; `nums.length == 2*n`.
- `-10^7 <= nums[i] <= 10^7`.
### Clarifying Questions
Each group must contain exactly n entries, and all original entries must be assigned.
```hint Inspect the structure
If you choose k entries from the first half, how many must you choose from the second?
```
### Reasoning checkpoints
- Use every input entry once and enforce the same number of entries in both groups.
- Justify that the reported difference is minimal over all valid divisions, including negative sums.
- Account for the full input size and use arithmetic wide enough for intermediate sums.
### Optional extensions
What alternative could reduce repeated search overhead without changing the equal-size requirement?
Overview: Split into Equal-Sized Groups with Closest Sums. The array nums has length 2n. Assign every entry to exactly one of two groups, each containing n entries. Return the smallest possible absolute difference between the two group sums. Entries can be negative.