Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Partition Array Into Two Arrays to Minimize Sum Difference

HARDProblemSolveExternal Links

Description

You are given an integer array nums containing exactly 2 * n integers. You need to partition nums into two arrays of length n each such that the absolute difference between the sums of the two arrays is minimized.

Every element of nums must go into exactly one of the two arrays, and both arrays must contain exactly n elements.

Return the minimum possible absolute difference between the sums of the two arrays.

Key observations:

  • The partition must be balanced — both resulting arrays have the same length n.
  • Elements can be negative, zero, or positive.
  • You are choosing which n elements go into the first array; the remaining n automatically form the second array.
  • If the total sum of all elements is S and the first array sums to A, the second array sums to S − A, and the difference is |A − (S − A)| = |2A − S|.

Examples

Example 1

Input: nums = [3, 9, 7, 3]

Output: 2

Explanation:
Here 2n = 4, so n = 2. We need to split into two arrays of 2 elements each.

One optimal partition: [3, 9] and [7, 3].

  • Sum of first array = 3 + 9 = 12
  • Sum of second array = 7 + 3 = 10
  • Absolute difference = |12 − 10| = 2

No partition achieves a difference smaller than 2.

Example 2

Input: nums = [-36, 36]

Output: 72

Explanation:
Here 2n = 2, so n = 1. Each array gets exactly one element.

The only partition is [-36] and [36] (or vice versa).

  • Absolute difference = |-36 − 36| = 72

With only two elements, there is no other choice.

Example 3

Input: nums = [2, -1, 0, 4, -2, -9]

Output: 0

Explanation:
Here 2n = 6, so n = 3. One optimal partition: [2, 4, -9] and [-1, 0, -2].

  • Sum of first = 2 + 4 + (-9) = -3
  • Sum of second = -1 + 0 + (-2) = -3
  • Absolute difference = |-3 − (-3)| = 0

A difference of 0 is the best possible — a perfect split!

Constraints

  • 1 ≤ n ≤ 15
  • nums.length == 2 * n
  • -10^7 ≤ nums[i] ≤ 10^7

Editorial

Brute Force

Intuition

The most direct approach: try every possible way to choose n elements from the 2n elements for the first array. The remaining n elements automatically form the second array.

Imagine you have 2n items on a table and two boxes. You must put exactly n items in each box. You try every possible combination for box 1, compute both sums, record the difference, and keep the smallest difference you find.

If the total sum of all elements is S, and the first array sums to A, the second sums to S − A, so the difference is |2A − S|. We just need to find the subset of size n whose sum A makes |2A − S| as small as possible.

Step-by-Step Explanation

Let us trace Example 1: nums = [3, 9, 7, 3], n = 2, total = 22.

We need to choose 2 elements out of 4 for the first array. There are C(4,2) = 6 combinations:

Step 1: Select indices {0, 1} → first = [3, 9], sum = 12. Diff = |2×12 − 22| = |24 − 22| = 2. min_diff = 2.

Step 2: Select indices {0, 2} → first = [3, 7], sum = 10. Diff = |20 − 22| = 2. min_diff stays 2.

Step 3: Select indices {0, 3} → first = [3, 3], sum = 6. Diff = |12 − 22| = 10. Much worse! min_diff stays 2.

Step 4: Select indices {1, 2} → first = [9, 7], sum = 16. Diff = |32 − 22| = 10. Also bad. min_diff stays 2.

Step 5: Select indices {1, 3} → first = [9, 3], sum = 12. Diff = 2. Tied with the best.

Step 6: Select indices {2, 3} → first = [7, 3], sum = 10. Diff = 2. Again tied.

Result: min_diff = 2. We examined all 6 combinations. Four of them achieve the minimum difference of 2.

Brute Force — Enumerate All C(2n, n) Combinations — Watch how the brute force systematically selects every possible pair of 2 elements from the 4-element array, computes the partition difference, and tracks the minimum.

Algorithm

  1. Compute total = sum(nums) and set min_diff = ∞.
  2. Generate all C(2n, n) ways to choose n elements from the array.
  3. For each combination:
    a. Compute sum_A = sum of the selected n elements.
    b. Compute diff = |2 × sum_A − total|.
    c. Update min_diff = min(min_diff, diff).
  4. Return min_diff.

Code

#include <vector>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <climits>
using namespace std;

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size() / 2;
        long long total = accumulate(nums.begin(), nums.end(), 0LL);
        long long minDiff = LLONG_MAX;

        // Recursively choose n elements for group A
        function<void(int, int, long long)> solve = [&](int idx, int cnt, long long sumA) {
            if (cnt == n) {
                minDiff = min(minDiff, abs(2 * sumA - total));
                return;
            }
            if (idx >= (int)nums.size()) return;
            if ((int)nums.size() - idx < n - cnt) return; // pruning
            solve(idx + 1, cnt + 1, sumA + nums[idx]); // include
            solve(idx + 1, cnt, sumA);                  // exclude
        };

        solve(0, 0, 0);
        return (int)minDiff;
    }
};
from itertools import combinations

class Solution:
    def minimumDifference(self, nums: list[int]) -> int:
        n = len(nums) // 2
        total = sum(nums)
        min_diff = float('inf')

        for combo in combinations(range(2 * n), n):
            sum_a = sum(nums[i] for i in combo)
            diff = abs(2 * sum_a - total)
            min_diff = min(min_diff, diff)

        return min_diff
class Solution {
    long minDiff;

    public int minimumDifference(int[] nums) {
        int n = nums.length / 2;
        long total = 0;
        for (int x : nums) total += x;
        minDiff = Long.MAX_VALUE;
        solve(nums, 0, 0, 0, n, total);
        return (int) minDiff;
    }

    private void solve(int[] nums, int idx, int cnt, long sumA, int n, long total) {
        if (cnt == n) {
            minDiff = Math.min(minDiff, Math.abs(2 * sumA - total));
            return;
        }
        if (idx >= nums.length || nums.length - idx < n - cnt) return;
        solve(nums, idx + 1, cnt + 1, sumA + nums[idx], n, total);
        solve(nums, idx + 1, cnt, sumA, n, total);
    }
}

Complexity Analysis

Time Complexity: O(C(2n, n) × n)

We enumerate all C(2n, n) ways to choose n elements from 2n. For each, computing the sum costs O(n). Using Stirling's approximation, C(2n, n) ≈ 4^n / √(πn). For n = 15: C(30, 15) ≈ 155,117,520. Multiplied by 15 ≈ 2.3 × 10^9 operations — far beyond any reasonable time limit.

Space Complexity: O(n)

The recursive call stack goes at most 2n levels deep. No additional data structures needed beyond a few tracking variables.

Why This Approach Is Not Efficient

The brute force tries all C(2n, n) possible partitions. This combinatorial number grows extremely fast:

n2nC(2n, n)Operations (× n)
5102521,260
1020184,7561,847,560
1530155,117,5202,326,762,800

At n = 15, we need over 2.3 billion operations. Even with aggressive pruning, this is catastrophically slow.

The fundamental problem is that we examine the entire array as one unit. Each subset selection considers all 2n elements together, so the search space is C(2n, n) — which grows as 4^n / √n.

Key insight (Meet-in-the-Middle): What if we split the array in half? Instead of one search space of size C(2n, n) ≈ 4^n, we get two search spaces of size 2^n each. For n = 15, that is 2 × 32,768 = 65,536 — a reduction from 155 million to 65 thousand. After precomputing all possible contributions from each half, we can combine them using binary search, turning an intractable problem into a fast one.

Bar chart comparing brute force C(2n,n) operations versus meet-in-the-middle 2^n operations for n=15
Bar chart comparing brute force C(2n,n) operations versus meet-in-the-middle 2^n operations for n=15

Optimal Approach - Meet-in-the-Middle with Binary Search

Intuition

Imagine you have 30 items to sort into two equal boxes and you want the weights as close as possible. Trying all ways to split 30 items is hopeless. But what if you split the items into two piles of 15 first?

Pile A (first 15 items): For every possible way to choose k items from this pile for box 1, compute the "contribution" — how much heavier box 1 becomes compared to box 2 due to this pile alone. If an item goes to box 1, it adds to the contribution; if to box 2, it subtracts. Store all contributions grouped by k.

Pile B (last 15 items): Do the same thing.

Combining: If we put k items from pile A into box 1, we must put exactly (n − k) from pile B into box 1 to reach n total. The overall difference = contribution_A + contribution_B. We want this as close to zero as possible.

For each contribution a from pile A, we need contribution b from pile B such that a + b ≈ 0, i.e., b ≈ −a. If pile B's contributions are sorted, finding the closest value to −a is a binary search — O(log(2^n)) = O(n) per query.

This "split, precompute, combine" strategy is called Meet-in-the-Middle. It reduces the search space from 4^n (brute force on full array) to 2 × 2^n (enumerate each half) plus O(2^n × n) for combining.

Step-by-Step Explanation

Let us trace Example 1: nums = [3, 9, 7, 3], n = 2.

Phase 1 — Split: Left half = [3, 9], Right half = [7, 3].

Phase 2 — Enumerate left subsets: For each bitmask 0..3 (2^2 = 4 subsets), compute contribution = sum(selected) − sum(unselected), grouped by count.

MaskSelectedUnselectedContributionCount
00{}{3,9}0−3−9 = −120
01{3}{9}3−9 = −61
10{9}{3}9−3 = 61
11{3,9}{}3+9 = 122

f[0] = {−12}, f[1] = {−6, 6}, f[2] = {12}

Phase 3 — Enumerate right subsets: Same process for [7, 3].

MaskSelectedUnselectedContributionCount
00{}{7,3}−7−3 = −100
01{7}{3}7−3 = 41
10{3}{7}3−7 = −41
11{7,3}{}7+3 = 102

g[0] = {−10}, g[1] = {−4, 4} (sorted), g[2] = {10}

Phase 4 — Combine using binary search:

Step 1 (i=0): Pick 0 from left, 2 from right. Pair f[0] with g[2].

  • a = −12 from f[0], search g[2] = [10]: only value is 10.
  • |−12 + 10| = 2. min_diff = 2.

Step 2 (i=1): Pick 1 from left, 1 from right. Pair f[1] with g[1].

  • Sort: f[1] = [−6, 6], g[1] = [−4, 4].
  • a = −6, want b closest to 6 in [−4, 4]. Binary search → closest is 4. |−6 + 4| = 2.
  • a = 6, want b closest to −6 in [−4, 4]. Binary search → closest is −4. |6 + (−4)| = 2.
  • min_diff stays 2.

Step 3 (i=2): Pick 2 from left, 0 from right. Pair f[2] with g[0].

  • a = 12 from f[2], search g[0] = [−10]: |12 + (−10)| = 2.
  • min_diff stays 2.

Result: min_diff = 2. We performed ~6 binary-search probes across all i values, compared to 6 full-combo evaluations in brute force. For n = 15 the savings are enormous: ~500K probes vs ~155M combos.

Meet-in-the-Middle — Precompute Halves, Combine with Binary Search — Watch how we enumerate subset contributions for each half, then use binary search in the combining step to find the closest matching contribution that minimizes the total difference.

Algorithm

  1. Let n = len(nums) / 2. Split nums into left[0..n-1] and right[n..2n-1].
  2. Enumerate left half: For each bitmask mask from 0 to 2^n − 1:
    • Compute contribution: for each bit j, if set → add left[j], else → subtract left[j].
    • Count how many bits are set → cnt.
    • Store contribution in f[cnt].
  3. Enumerate right half: Same process → store in g[cnt].
  4. Sort every list in g for binary search.
  5. Combine: For each i from 0 to n:
    • For each value a in f[i]:
      • Binary search in g[n − i] for the value b closest to −a.
      • Update min_diff = min(min_diff, |a + b|).
      • Also check the neighbor of the binary search result (to handle the "floor vs. ceil" case).
  6. Return min_diff.

Code

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstdlib>
#include <climits>
using namespace std;

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size() / 2;
        unordered_map<int, vector<int>> f, g;

        // Enumerate left half subsets
        for (int mask = 0; mask < (1 << n); mask++) {
            int s = 0, cnt = 0;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) { s += nums[j]; cnt++; }
                else { s -= nums[j]; }
            }
            f[cnt].push_back(s);
        }

        // Enumerate right half subsets
        for (int mask = 0; mask < (1 << n); mask++) {
            int s = 0, cnt = 0;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) { s += nums[n + j]; cnt++; }
                else { s -= nums[n + j]; }
            }
            g[cnt].push_back(s);
        }

        // Sort right-half groups for binary search
        for (auto& [k, v] : g) sort(v.begin(), v.end());

        long long minDiff = LLONG_MAX;

        // Combine: for i elements from left, n-i from right
        for (int i = 0; i <= n; i++) {
            for (int a : f[i]) {
                auto& rv = g[n - i];
                int target = -a;
                auto it = lower_bound(rv.begin(), rv.end(), target);
                if (it != rv.end())
                    minDiff = min(minDiff, (long long)abs(a + *it));
                if (it != rv.begin())
                    minDiff = min(minDiff, (long long)abs(a + *prev(it)));
            }
        }

        return (int)minDiff;
    }
};
from collections import defaultdict
from bisect import bisect_left

class Solution:
    def minimumDifference(self, nums: list[int]) -> int:
        n = len(nums) // 2

        f = defaultdict(list)  # left half: count -> contributions
        g = defaultdict(list)  # right half: count -> contributions

        # Enumerate left half subsets
        for mask in range(1 << n):
            s, cnt = 0, 0
            for j in range(n):
                if mask & (1 << j):
                    s += nums[j]; cnt += 1
                else:
                    s -= nums[j]
            f[cnt].append(s)

        # Enumerate right half subsets
        for mask in range(1 << n):
            s, cnt = 0, 0
            for j in range(n):
                if mask & (1 << j):
                    s += nums[n + j]; cnt += 1
                else:
                    s -= nums[n + j]
            g[cnt].append(s)

        # Sort right-half groups for binary search
        for k in g:
            g[k].sort()

        min_diff = float('inf')

        # Combine: for i from left, n-i from right
        for i in range(n + 1):
            for a in f[i]:
                rv = g[n - i]
                target = -a
                pos = bisect_left(rv, target)
                if pos < len(rv):
                    min_diff = min(min_diff, abs(a + rv[pos]))
                if pos > 0:
                    min_diff = min(min_diff, abs(a + rv[pos - 1]))

        return min_diff
import java.util.*;

class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length / 2;
        Map<Integer, List<Integer>> f = new HashMap<>();
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int k = 0; k <= n; k++) {
            f.put(k, new ArrayList<>());
            g.put(k, new ArrayList<>());
        }

        // Enumerate left half subsets
        for (int mask = 0; mask < (1 << n); mask++) {
            int s = 0, cnt = 0;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) { s += nums[j]; cnt++; }
                else { s -= nums[j]; }
            }
            f.get(cnt).add(s);
        }

        // Enumerate right half subsets
        for (int mask = 0; mask < (1 << n); mask++) {
            int s = 0, cnt = 0;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) { s += nums[n + j]; cnt++; }
                else { s -= nums[n + j]; }
            }
            g.get(cnt).add(s);
        }

        for (List<Integer> list : g.values()) Collections.sort(list);

        long minDiff = Long.MAX_VALUE;

        for (int i = 0; i <= n; i++) {
            List<Integer> rv = g.get(n - i);
            for (int a : f.get(i)) {
                int target = -a;
                int pos = Collections.binarySearch(rv, target);
                if (pos < 0) pos = -pos - 1;
                if (pos < rv.size())
                    minDiff = Math.min(minDiff, Math.abs((long) a + rv.get(pos)));
                if (pos > 0)
                    minDiff = Math.min(minDiff, Math.abs((long) a + rv.get(pos - 1)));
            }
        }

        return (int) minDiff;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

Enumeration: We iterate over 2^n bitmasks for each half. For each mask, we do O(n) work to compute the contribution. Total enumeration: 2 × 2^n × n = O(n × 2^n).

Sorting: The total number of entries across all groups in g is 2^n. Sorting all of them takes O(2^n × log(2^n)) = O(n × 2^n).

Combining: For each of the n+1 values of i, we iterate over all entries in f[i] (total across all i = 2^n entries) and perform a binary search in the corresponding g[n−i] list. Each binary search takes O(log(2^n)) = O(n). Total: 2^n × n = O(n × 2^n).

Overall: O(n × 2^n). For n = 15: 15 × 32,768 ≈ 500,000 — easily under one second.

Space Complexity: O(2^n)

We store 2^n entries in f and 2^n entries in g. The sorted copies are in-place. Overall: O(2^n). For n = 15: 32,768 entries per half — very modest.