Partition Array Into Two Arrays to Minimize Sum Difference

Hard Recursion & Backtracking Meet in the Middle Original on LeetCode

Partition Array Into Two Arrays to Minimize Sum Difference is a hard recursion & backtracking problem solved with the meet in the middle pattern. The best approach, optimal (meet in the middle), runs in O(2^n · n) time and O(2^n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pick / not pick) up.

Problem

You are given an integer array nums of even length 2 * n. Split it into two arrays of exactly n elements each, so that every element goes into exactly one of them.

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

Examples

Example 1

Input
nums = [5, 9, 2, 6]
Output
0
Why
Split into [5, 6] and [9, 2]: both sum to 11.

Example 2

Input
nums = [-8, 4]
Output
12
Why
Each half holds one number, so the only split gives |-8 - 4| = 12.

Example 3

Input
nums = [10, -3, 7, 1, -6, 2]
Output
1
Why
The total is 11, which is odd, so 0 is impossible. [10, 1, -6] sums to 5 and [-3, 7, 2] sums to 6.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (pick / not pick)O(2^(2n))O(n)
Optimal (meet in the middle)O(2^n · n)O(2^n)

1Brute force (pick / not pick)

TimeO(2^(2n))Up to two choices for each of the 2n elements; pruning only trims the tree to about C(2n, n) leaves.
SpaceO(n)The recursion depth is 2n.

Decide for every element whether it goes into the first half, keeping a count and a running sum. When all elements are decided and exactly n were picked, the difference is |total - 2 * sum|. Prune branches that already picked too many or can no longer reach n.

  1. Compute total = sum of nums.
  2. dfs(i, count, sum): if count > n or count + (2n - i) < n, stop.
  3. At i == 2n, update best with |total - 2 * sum|.
  4. Otherwise recurse with nums[i] picked and not picked.
class Solution {
    private int best;

    public int minimumDifference(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        best = Integer.MAX_VALUE;
        dfs(nums, 0, 0, 0, total);
        return best;
    }

    private void dfs(int[] nums, int i, int count, int sum, int total) {
        int m = nums.length, n = m / 2;
        if (count > n || count + (m - i) < n) return;
        if (i == m) {
            best = Math.min(best, Math.abs(total - 2 * sum));
            return;
        }
        dfs(nums, i + 1, count + 1, sum + nums[i], total);
        dfs(nums, i + 1, count, sum, total);
    }
}

2Optimal (meet in the middle)

TimeO(2^n · n)2^n sums per part; sorting them and doing one O(log 2^n) = O(n) binary search per left sum.
SpaceO(2^n)The subset sums of both parts.

Cut the array into a left part and a right part of n elements each. For each part, list the sums of all its subsets, grouped by how many elements they use. A valid first half takes c elements from the left and n - c from the right. For every left sum a with size c, we want a right sum b of size n - c that makes 2 * (a + b) as close to total as possible. With each right group sorted, binary search for the first b where 2 * (a + b) >= total and also check the one just before it.

  1. Enumerate all 2^n subset sums of the left part and of the right part, grouped by subset size (sum[mask] = sum[mask without its lowest bit] + that element).
  2. Sort every group of the right part.
  3. For each size c and each left sum a in group c, binary search group n - c of the right part for the first b with 2 * (a + b) >= total.
  4. Update the answer with |total - 2 * (a + b)| for that b and for its predecessor.
class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length / 2, total = 0;
        for (int x : nums) total += x;
        List<List<Integer>> left = halfSums(nums, 0, n), right = halfSums(nums, n, n);
        for (List<Integer> group : right) Collections.sort(group);
        int best = Integer.MAX_VALUE;
        for (int c = 0; c <= n; c++) {
            List<Integer> r = right.get(n - c);
            for (int a : left.get(c)) {
                int lo = 0, hi = r.size();
                while (lo < hi) {
                    int mid = (lo + hi) >>> 1;
                    if (2 * (a + r.get(mid)) >= total) hi = mid;
                    else lo = mid + 1;
                }
                if (lo < r.size()) best = Math.min(best, Math.abs(total - 2 * (a + r.get(lo))));
                if (lo > 0) best = Math.min(best, Math.abs(total - 2 * (a + r.get(lo - 1))));
            }
        }
        return best;
    }

    private List<List<Integer>> halfSums(int[] nums, int start, int n) {
        List<List<Integer>> bySize = new ArrayList<>();
        for (int c = 0; c <= n; c++) bySize.add(new ArrayList<>());
        int[] sum = new int[1 << n];
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask > 0) {
                int low = Integer.numberOfTrailingZeros(mask);
                sum[mask] = sum[mask & (mask - 1)] + nums[start + low];
            }
            bySize.get(Integer.bitCount(mask)).add(sum[mask]);
        }
        return bySize;
    }
}

Edge cases to test

  • n = 1: there is only one way to split
  • Negative numbers, so sums are not monotone in the number of picked elements
  • All values equal: the answer is 0
  • An odd total: the answer is at least 1

Hints

Hint 1

If one half sums to s, the other sums to total - s, so the difference is |total - 2s|. You only have to choose the n elements of one half.

Hint 2

C(30, 15) is about 1.5 * 10^8 choices, too many. Split the array into a left and a right part of n elements each and enumerate subsets of each part separately (2^15 each).

Hint 3

If you take c elements from the left part, you must take n - c from the right. Group right-part sums by size, sort each group, and binary search for the sum that brings the total closest to total / 2.

FAQ

What is the best time complexity for Partition Array Into Two Arrays to Minimize Sum Difference?

Optimal (meet in the middle) runs in O(2^n · n) time and O(2^n) extra space. 2^n sums per part; sorting them and doing one O(log 2^n) = O(n) binary search per left sum.

Which pattern does Partition Array Into Two Arrays to Minimize Sum Difference use?

It is a recursion & backtracking problem that uses the meet in the middle pattern.

Is there a brute force solution for Partition Array Into Two Arrays to Minimize Sum Difference?

Yes. Brute force (pick / not pick) takes O(2^(2n)) time and O(n) space. Decide for every element whether it goes into the first half, keeping a count and a running sum.

Which edge cases should I test for Partition Array Into Two Arrays to Minimize Sum Difference?

n = 1: there is only one way to split; Negative numbers, so sums are not monotone in the number of picked elements; All values equal: the answer is 0; An odd total: the answer is at least 1.