Tug of War

The problem, simply

You get n numbers. Split them into two groups. If n is even, both groups have n / 2 numbers. If n is odd, one group has n / 2 and the other has one more.

Make the difference between the two group sums as small as possible. Give back that smallest difference (and, if asked, the two groups). Numbers may be negative.

A story to remember it

Picture it

Examples

Way 1: the simple way

Send every kid to team A or team B in every possible way. Only count the splits where team A has exactly n / 2 kids.

1. For kid i, branch twice: join team A, or join team B.
2. Carry team A's size and weight.
3. When every kid is placed, if team A has n / 2 kids, the difference is |total - 2 * sumA|. Keep the smallest.

class Solution {
    private int best;

    public int tugOfWar(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        best = Integer.MAX_VALUE;
        split(arr, 0, 0, 0, total);
        return best;
    }

    private void split(int[] arr, int i, int sizeA, int sumA, int total) {
        int n = arr.length;
        if (i == n) {
            if (sizeA == n / 2) best = Math.min(best, Math.abs(total - 2 * sumA));
            return;
        }
        split(arr, i + 1, sizeA + 1, sumA + arr[i], total);  // kid i joins team A
        split(arr, i + 1, sizeA, sumA, total);               // kid i joins team B
    }
}

How long it takes: two choices per kid, 2^n splits, and most have the wrong team size. O(2^n). Extra room: the call stack, O(n).

Way 2: the clever way

Only build splits with the right team size, and stop when the split is already perfect.

1. Pick team A's members one at a time, always from a later spot than the last pick. Then each team is built once, never in two orders.
2. Leave room: if team A still needs r more kids, the next pick can be at most at spot n - r.
3. When team A is full, compute the difference and keep the best team.
4. The difference can never be below total % 2 (0 for an even total, 1 for an odd one). If you reach it, stop everything.

import java.util.*;

class Solution {
    private int best;
    private List<Integer> bestTeam;

    public int tugOfWar(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        best = Integer.MAX_VALUE;
        pick(arr, 0, new ArrayList<>(), 0, total);
        return best;                                      // bestTeam holds team A's spots
    }

    private void pick(int[] arr, int start, List<Integer> team, int sumA, int total) {
        int n = arr.length, k = n / 2;
        if (team.size() == k) {
            int diff = Math.abs(total - 2 * sumA);
            if (diff < best) {
                best = diff;
                bestTeam = new ArrayList<>(team);
            }
            return;
        }
        int need = k - team.size();
        for (int i = start; i <= n - need; i++) {         // leave room for the rest
            team.add(i);
            pick(arr, i + 1, team, sumA + arr[i], total);
            team.remove(team.size() - 1);
            if (best == (total & 1)) return;              // perfect already, stop everything
        }
    }
}

How long it takes: only teams of the right size are built, C(n, n/2) of them, which is about 2^n / sqrt(n). With the running sum each team costs O(1), so O(C(n, n/2)), and the early stop often ends much sooner. Extra room: the team list and the call stack, O(n).

Another way: meet in the middle

For n up to about 40, even C(n, n/2) is too slow. Split the kids into a left half and a right half. List every subset of each half, grouped by how many kids it takes, about 2^(n/2) each. If team A takes i kids from the left, it needs k - i from the right, and the best right sum is the one closest to total / 2 - leftSum. Sort each group of right sums and binary search.

import java.util.*;

class Solution {
    public long tugOfWar(int[] arr) {
        int n = arr.length, k = n / 2, h = n / 2, m = n - h;
        long total = 0;
        for (int x : arr) total += x;

        List<List<Long>> right = new ArrayList<>();      // right half sums, by team size
        for (int j = 0; j <= m; j++) right.add(new ArrayList<>());
        for (int mask = 0; mask < (1 << m); mask++) {
            long s = 0;
            for (int b = 0; b < m; b++) if ((mask >> b & 1) == 1) s += arr[h + b];
            right.get(Integer.bitCount(mask)).add(s);
        }
        for (List<Long> list : right) Collections.sort(list);

        long best = Long.MAX_VALUE;
        for (int mask = 0; mask < (1 << h); mask++) {
            int j = k - Integer.bitCount(mask);          // kids still needed from the right
            if (j < 0 || j > m) continue;
            long s = 0;
            for (int b = 0; b < h; b++) if ((mask >> b & 1) == 1) s += arr[b];
            List<Long> list = right.get(j);
            int lo = 0, hi = list.size();                // first r with 2 * (s + r) >= total
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (2 * (s + list.get(mid)) >= total) hi = mid; else lo = mid + 1;
            }
            for (int p = lo - 1; p <= lo; p++) {         // check the neighbors around the middle
                if (p >= 0 && p < list.size()) best = Math.min(best, Math.abs(total - 2 * (s + list.get(p))));
            }
        }
        return best;
    }
}

This runs in O(2^(n/2) * n) time and O(2^(n/2)) room. For 40 kids that is about a million subsets per half, instead of 137 billion teams.

Watch out for

• Negative numbers. Do not prune with "team A is already too heavy", because a later negative number can bring it back down.
• Odd n. Team A gets n / 2 kids and team B gets the rest. Both ways around are covered, because team B is everyone not picked.
• Stopping early at difference 0 when the total is odd. The best possible is 1 then. Use total & 1, which is also safe for negative totals.

What interviewers ask next

• Can you halve the work? When n is even, swapping the two teams gives the same split. Put kid 0 in team A always, and choose only the other n / 2 - 1 members.
• What if the numbers are small and positive? Use a table can[c][s]: can we pick c kids that weigh s? Fill it like subset sum with an extra count. That is O(n^2 * total).
• What if team sizes do not matter? Then it is the minimum subset sum difference problem: fill a subset sum table up to total / 2 and take the biggest reachable sum.
• Return the teams too. Keep bestTeam as in Way 2. Team B is everyone not in it.

Remember this

Grown-up words: picking members in increasing order generates combinations, leaving room and the early stop are pruning, the whole thing is backtracking, and splitting into halves with sorted lists and binary search is meet in the middle.