# Partition Array Into Two Arrays to Minimize Sum Difference
**Difficulty:** HARD
[External](https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-into-two-arrays-to-minimize-sum-difference
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Ordered Set
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [Salesforce](https://scaleengineer.com/companies/salesforce), [PhonePe](https://scaleengineer.com/companies/phonepe), [Millennium](https://scaleengineer.com/companies/millennium), [Texas Instruments](https://scaleengineer.com/companies/texas-instruments), [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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:**

![example-1](https://assets.glich.co/dsa/partition-array-into-two-arrays-to-minimize-sum-difference/image0.png) 

**Input:** 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:**

**Input:** 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:**

![example-3](https://assets.glich.co/dsa/partition-array-into-two-arrays-to-minimize-sum-difference/image1.png) 

**Input:** 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.

**Constraints:**

* `1 <= n <= 15`
* `nums.length == 2 * n`
* `-107 <= nums[i] <= 107`

# Approaches
## Brute Force with Recursion
This approach explores all possible ways to partition the array `nums` into two subarrays of size `n`. We can use recursion to generate every possible subset of size `n` for the first array. For each such partition, we calculate the sum of both arrays and find their absolute difference. We keep track of the minimum difference found across all partitions.
**Time:** O(C(2*n, n)). The recursion tree explores all combinations of choosing `n` elements from `2*n`. For `n=15`, `C(30, 15)` is approximately `1.55 * 10^8`, which is very slow. · **Space:** O(n) for the recursion stack depth, as the maximum depth of the recursion is `2*n`.
**Pros:** Simple to understand and implement.; It's a direct translation of the problem statement.
**Cons:** Extremely inefficient for the given constraints.; Will likely result in a "Time Limit Exceeded" error on most platforms.
### Explanation
The problem is to find a subset of `n` elements from the `2*n` elements such that its sum, let's call it `sum1`, makes the value `| (totalSum - sum1) - sum1 | = |totalSum - 2 * sum1|` as small as possible. We can define a recursive function, say `findMinDiff(index, count, currentSum)`, which tries to build the first partition.

- `index`: The current index in the `nums` array we are considering.
- `count`: The number of elements already chosen for the first partition.
- `currentSum`: The sum of elements chosen so far.

The recursion explores two choices for each element: either include it in the first partition or not. The base case for the recursion is when we have chosen `n` elements (`count == n`). At this point, we have a valid partition, and we calculate the difference `|totalSum - 2 * currentSum|` and update our global minimum. We also need pruning conditions to avoid unnecessary computations. For example, if the number of elements left to choose from is less than the number of elements we still need to pick, we can stop that recursive path.

```java
class Solution {
    int minDiff = Integer.MAX_VALUE;
    int totalSum = 0;
    int n;

    public int minimumDifference(int[] nums) {
        this.n = nums.length / 2;
        for (int num : nums) {
            this.totalSum += num;
        }
        findMinDiff(0, 0, 0, nums);
        return minDiff;
    }

    private void findMinDiff(int index, int count, int currentSum, int[] nums) {
        // Pruning: if remaining elements are not enough to form a partition of size n
        if (n - count > nums.length - index) {
            return;
        }

        if (count == n) {
            int sum2 = totalSum - currentSum;
            minDiff = Math.min(minDiff, Math.abs(currentSum - sum2));
            return;
        }

        if (index == nums.length) {
            return;
        }

        // Include nums[index]
        findMinDiff(index + 1, count + 1, currentSum + nums[index], nums);

        // Exclude nums[index]
        findMinDiff(index + 1, count, currentSum, nums);
    }
}
```
### Algorithm
- Calculate `totalSum` of all elements in `nums`.
- Initialize `minDifference` to a very large value.
- Define a recursive function `solve(index, count, sum1)`:
  - If `count == n`:
    - `sum2 = totalSum - sum1`.
    - `minDifference = min(minDifference, abs(sum1 - sum2))`.
    - Return.
  - If `index == 2*n`:
    - Return.
  - To avoid TLE, add pruning: if the number of elements we still need to pick (`n - count`) is greater than the number of elements remaining in the array (`2*n - index`), we can prune this path.
  - **Include `nums[index]`**: Call `solve(index + 1, count + 1, sum1 + nums[index])`.
  - **Exclude `nums[index]`**: Call `solve(index + 1, count, sum1)`.
- Call `solve(0, 0, 0)`.
- Return `minDifference`.

## Meet-in-the-Middle
This approach significantly improves upon the brute-force method by using a divide-and-conquer strategy known as "meet-in-the-middle". The array `nums` of size `2*n` is split into two halves, each of size `n`. We generate all possible subset sums for both halves independently. Then, we combine the sums from the two halves to find the partition that minimizes the sum difference.
**Time:** O(n * 2^n). Generating the sums for each half takes `O(2^n)`. The combination step involves iterating through `k` from `0` to `n`. For each `k`, we iterate through `C(n, k)` sums and perform a binary search on a list of size `C(n, n-k)`. The total time is dominated by `sum_{k=0 to n} C(n, k) * log(C(n, k))`, which is roughly `O(n * 2^n)`. · **Space:** O(2^n). We need to store all possible subset sums for both halves. The total number of sums is `2 * sum_{k=0 to n} C(n, k) = 2 * 2^n`.
**Pros:** Much more efficient than brute force and feasible for the given constraints (`n <= 15`).; A classic and powerful technique for problems with this structure and input size.
**Cons:** More complex to implement than the brute-force approach.; Requires significant memory to store the subset sums.
### Explanation
The core idea is to reduce the exponential complexity from `O(C(2n, n))` to `O(n * 2^n)`. First, we split the `nums` array into a `left_half` (first `n` elements) and a `right_half` (last `n` elements). Next, we generate all possible sums for subsets of any size `k` (from 0 to `n`) for both halves. We can store these sums in a list of sets, where `sums[k]` contains all possible sums of `k` elements. This generation can be done with a recursive function, taking `O(2^n)` time for each half.

Our goal is to form a partition of size `n` with a sum `S` that is as close as possible to `totalSum / 2`. This partition will be formed by picking `k` elements from the `left_half` and `n-k` elements from the `right_half`. We iterate through `k` from `0` to `n`. For each `k`, we take a sum `s1` from `left_sums[k]`. We then need to find a sum `s2` from `right_sums[n-k]` such that `s1 + s2` is closest to `totalSum / 2`. This is equivalent to finding `s2` closest to `(totalSum / 2) - s1`. To find the closest `s2` efficiently, we can sort the list of sums from `right_sums[n-k]` and use binary search for each `s1`. For each combination of `s1` and `s2`, we calculate the partition sum `S = s1 + s2` and update our minimum difference with `|totalSum - 2*S|`.

```java
import java.util.*;

class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length / 2;
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        List<Set<Integer>> leftSums = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            leftSums.add(new HashSet<>());
        }
        generate(0, 0, 0, nums, n, leftSums);

        List<Set<Integer>> rightSums = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            rightSums.add(new HashSet<>());
        }
        generate(n, 0, 0, nums, 2 * n, rightSums);

        int minDiff = Integer.MAX_VALUE;
        for (int k = 0; k <= n; k++) {
            List<Integer> s1List = new ArrayList<>(leftSums.get(k));
            List<Integer> s2List = new ArrayList<>(rightSums.get(n - k));
            Collections.sort(s2List);

            for (int s1 : s1List) {
                int targetS2 = (totalSum / 2) - s1;
                int idx = Collections.binarySearch(s2List, targetS2);

                if (idx >= 0) {
                    int partitionSum = s1 + s2List.get(idx);
                    minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum));
                } else {
                    int insertionPoint = -idx - 1;
                    if (insertionPoint < s2List.size()) {
                        int partitionSum = s1 + s2List.get(insertionPoint);
                        minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum));
                    }
                    if (insertionPoint > 0) {
                        int partitionSum = s1 + s2List.get(insertionPoint - 1);
                        minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * partitionSum));
                    }
                }
            }
        }
        return minDiff;
    }

    private void generate(int index, int count, int currentSum, int[] nums, int end, List<Set<Integer>> sums) {
        if (index == end) {
            sums.get(count).add(currentSum);
            return;
        }
        // Exclude nums[index]
        generate(index + 1, count, currentSum, nums, end, sums);
        // Include nums[index]
        generate(index + 1, count + 1, currentSum + nums[index], nums, end, sums);
    }
}
```
### Algorithm
- Split `nums` into two halves, `left_part` and `right_part`, each of size `n`.
- For `left_part`, generate all possible subset sums for each possible subset size (`0` to `n`). Store them in `left_sums`, where `left_sums[k]` is a set of sums of subsets of size `k`.
- Do the same for `right_part` and store them in `right_sums`.
- Calculate `totalSum`. Initialize `min_diff` to infinity.
- Iterate `k` from `0` to `n`.
  - Let `sums1` be the list of sums from `left_sums[k]`.
  - Let `sums2` be the list of sums from `right_sums[n-k]`.
  - Sort `sums2`.
  - For each `s1` in `sums1`:
    - Calculate the target for the second sum: `target_s2 = (totalSum / 2) - s1`.
    - Use binary search on `sums2` to find the value closest to `target_s2`. Let this be `s2`.
    - The partition sum is `S = s1 + s2`.
    - Update `min_diff = min(min_diff, abs(totalSum - 2 * S))`.
- Return `min_diff`.

# Solutions
### Java

```java
class Solution {
public
  int minimumDifference(int[] nums) {
    int n = nums.length >> 1;
    Map<Integer, Set<Integer>> f = new HashMap<>();
    Map<Integer, Set<Integer>> g = new HashMap<>();
    for (int i = 0; i < (1 << n); ++i) {
      int s = 0, cnt = 0;
      int s1 = 0, cnt1 = 0;
      for (int j = 0; j < n; ++j) {
        if ((i & (1 << j)) != 0) {
          s += nums[j];
          ++cnt;
          s1 += nums[n + j];
          ++cnt1;
        } else {
          s -= nums[j];
          s1 -= nums[n + j];
        }
      }
      f.computeIfAbsent(cnt, k->new HashSet<>()).add(s);
      g.computeIfAbsent(cnt1, k->new HashSet<>()).add(s1);
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i <= n; ++i) {
      List<Integer> fi = new ArrayList<>(f.get(i));
      List<Integer> gi = new ArrayList<>(g.get(n - i));
      Collections.sort(fi);
      Collections.sort(gi);
      for (int a : fi) {
        int left = 0, right = gi.size() - 1;
        int b = -a;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (gi.get(mid) >= b) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        ans = Math.min(ans, Math.abs(a + gi.get(left)));
        if (left > 0) {
          ans = Math.min(ans, Math.abs(a + gi.get(left - 1)));
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumDifference(vector<int> &nums) {
    int n = nums.size() >> 1;
    vector<vector<int>> f(n + 1), g(n + 1);
    for (int i = 0; i < (1 << n); ++i) {
      int s = 0, cnt = 0;
      int s1 = 0, cnt1 = 0;
      for (int j = 0; j < n; ++j) {
        if (i & (1 << j)) {
          s += nums[j];
          ++cnt;
          s1 += nums[n + j];
          ++cnt1;
        } else {
          s -= nums[j];
          s1 -= nums[n + j];
        }
      }
      f[cnt].push_back(s);
      g[cnt1].push_back(s1);
    }
    for (int i = 0; i <= n; ++i) {
      sort(f[i].begin(), f[i].end());
      sort(g[i].begin(), g[i].end());
    }
    int ans = INT_MAX;
    for (int i = 0; i <= n; ++i) {
      for (int a : f[i]) {
        int left = 0, right = g[n - i].size() - 1;
        int b = -a;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (g[n - i][mid] >= b)
            right = mid;
          else
            left = mid + 1;
        }
        ans = min(ans, abs(a + g[n - i][left]));
        if (left > 0)
          ans = min(ans, abs(a + g[n - i][left - 1]));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    # min(abs(f[i] + g[n - i])) for a in fi : left , right = 0 , len ( gi ) - 1 b = - a while left < right : mid = ( left + right ) >> 1 if gi [ mid ] >= b : right = mid else : left = mid + 1 ans = min ( ans , abs ( a + gi [ left ])) if left > 0 : ans = min ( ans , abs ( a + gi [ left - 1 ])) return ans
    def minimumDifference(self, nums: List[int]) -> int: n = len(nums) >> 1 f = defaultdict(set) g = defaultdict(set) for i in range(1 << n): s = cnt = 0 s1 = cnt1 = 0 for j in range(n): if (i & (1 << j)) != 0: s += nums[j] cnt += 1 s1 += nums[n + j] cnt1 += 1 else: s -= nums[j] s1 -= nums[n + j] f[cnt]. add(s) g[cnt1]. add(s1) ans = inf for i in range(n + 1): fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))

```