Command Palette

Search for a command to run...

Hectal
Problem 38.6 · Advanced Search and Divide & ConquerHard

Partition Array Into Two Arrays to Minimize Sum Difference

PatternDivide and ConquerBinary Search on an Index

What it teaches: Meet in the middle grouped by how many items each half contributes.

Practise it on judges as “Partition Array Into Two Arrays to Minimize Sum Difference”.

In plain words

Split a team of 2n players into two equal-sized teams so their total strengths are as close as possible. Split the list into a left half and a right half. If team A takes k players from the left half, it must take n − k from the right half. List the totals by how many players were chosen, then for each left total binary-search the right list for the partner that makes team A closest to half of everything.

Return the smallest possible difference. Example: nums = [3, 9, 7, 3] → 2.

The problem

nums has 2n elements. Split it into two arrays of n elements each to minimise the absolute difference of their sums.

Example 1

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

[3, 9] and [7, 3]: 12 vs 10.

Constraints

  • 1 ≤ n ≤ 15
  • |nums[i]| ≤ 10⁷

Pattern clues in the wording

  • → 2n ≤ 30 elements
  • → Equal-size split

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public int minimumDifference(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [3,9,7,3]
2
2
nums = [-36,36]
72
3
nums = [2,-1,0,4,-2,-9]
0

From slow to fast

Approaches

1. Meet in the middle by subset size · O(2ⁿ × n)
1

Meet in the middle by subset size

Time O(2ⁿ × n) Space O(2ⁿ)

For each half, list subset sums by count. For k = 0..n, sort right[n − k]; for each a in left[k], find b closest to (total − 2a) / 2; the difference is |total − 2(a + b)|.

▶ Dry run: Meet in the middle, grouped by sizenums = [3, 9, 7, 3]
3
0
9
1
7
2
3
3

left [3, 9] by size(map)

0: [0]1: [3, 9]2: [12]

right [7, 3] by size(map)

0: [0]1: [7, 3]2: [10]

vars(vars)

n: 2total: 22

Step 1/4Team A needs 2 players. The total is 22, so ideally team A has 11.

Approach 1
import java.util.*;

class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length / 2;
        long total = 0;
        for (int x : nums) total += x;
        List<List<Long>> left = bySize(nums, 0, n), right = bySize(nums, n, 2 * n);
        long best = Long.MAX_VALUE;
        for (int k = 0; k <= n; k++) {
            List<Long> r = right.get(n - k);
            Collections.sort(r);
            for (long a : left.get(k)) {
                double want = (total - 2.0 * a) / 2;            // ideal b
                int lo = 0, hi = r.size();
                while (lo < hi) {
                    int mid = (lo + hi) >>> 1;
                    if (r.get(mid) < want) lo = mid + 1; else hi = mid;
                }
                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 (int) best;
    }

    private List<List<Long>> bySize(int[] nums, int from, int to) {
        int m = to - from;
        List<List<Long>> out = new ArrayList<>();
        for (int i = 0; i <= m; i++) out.add(new ArrayList<>());
        for (int mask = 0; mask < (1 << m); mask++) {
            long s = 0;
            for (int i = 0; i < m; i++) if (((mask >> i) & 1) == 1) s += nums[from + i];
            out.get(Integer.bitCount(mask)).add(s);
        }
        return out;
    }
}

Verdict: The size grouping keeps the split balanced.

Before you submit

Edge cases and common mistakes

Test these inputs

  • n = 1
  • Negative numbers

Mistakes people make

  • Ignoring sizes (gives an unbalanced split).

Interview

Follow-up questions

Why not the partition-equal-subset DP?