Partition problem

The problem, simply

You get a list of positive numbers. Can you put every number into one of two groups so that both groups add up to the same total? Answer yes or no.

The trick to see first: if both groups are equal, each one is exactly half of the grand total. So the question becomes "can some of the numbers add up to half the total?" If the total is odd, the answer is no right away.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the half, then try every pick. Go through the numbers one by one, and for each one ask two helpers: "can the rest make it if I put this one in?" and "can the rest make it if I leave this one out?"

1. Add up everything. If the total is odd, return false. Otherwise need = total / 2.
2. can(i, need): if need is 0, yes. If no numbers are left, no.
3. Otherwise, yes if can(i + 1, need - a[i]) (put it in, only if it fits) or can(i + 1, need) (leave it out).

class Solution {
    public boolean canPartition(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        if (total % 2 != 0) return false;          // odd total: no fair split
        return can(arr, 0, total / 2);
    }

    private boolean can(int[] arr, int i, int need) {
        if (need == 0) return true;                 // plate is exactly right
        if (i == arr.length) return false;          // nothing left to try
        if (arr[i] <= need && can(arr, i + 1, need - arr[i])) return true;  // put it in
        return can(arr, i + 1, need);                                       // leave it out
    }
}

How long it takes: each number has two choices, so up to O(2^n) tries. Extra room: the call chain, O(n).

Way 2: the clever way

The helper only depends on two small numbers: how many items you have looked at, and how much weight is still needed. Put every answer in a table.

1. can[i][s] is true when some of the first i numbers add up to exactly s.
2. can[0][0] is true (no numbers, empty plate). Every other cell in row 0 is false.
3. For number x in row i: can[i][s] = can[i-1][s] (leave it out) or, if x <= s, can[i-1][s-x] (put it in).
4. The answer is can[n][total / 2].

class Solution {
    public boolean canPartition(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        if (total % 2 != 0) return false;
        int half = total / 2;
        int n = arr.length;

        boolean[][] can = new boolean[n + 1][half + 1];
        for (int i = 0; i <= n; i++) can[i][0] = true;    // the empty plate

        for (int i = 1; i <= n; i++) {
            int x = arr[i - 1];
            for (int s = 1; s <= half; s++) {
                can[i][s] = can[i - 1][s];                  // leave x out
                if (x <= s && can[i - 1][s - x]) {
                    can[i][s] = true;                       // put x in
                }
            }
        }
        return can[n][half];
    }
}

How long it takes: one cell per (number, sum) pair, O(n * sum) where sum is half the total. Extra room: the table, O(n * sum).

Watch out for

• The table is only fast when the numbers are small. With numbers in the billions, sum is huge and the table does not fit. Then the exponential way (or meet in the middle) is all you have.
• In the one row version below, loop s from high to low. Going low to high lets one number be used twice.
• A single number can never be split, unless it is 0.

What interviewers ask next

• Can you use one row instead of a table? Yes. Keep can[s] and for each number loop s from half down to x: can[s] = can[s] || can[s - x]. Extra room drops to O(sum).
• Can you make it faster in practice? Store the row as bits and do bits |= bits << x for each number. That checks 64 sums per step.
• Split into two groups with the smallest possible difference. Fill the same table for all sums up to total / 2, then take the biggest reachable s. The difference is total - 2s.
• Split into k equal groups. That is much harder (LeetCode 698). Use backtracking with pruning, or DP over subsets with bitmasks.

Remember this

Grown-up words: the plate weight is the target sum, the yes or no table is the subset sum DP table, putting in or leaving out is the 0/1 knapsack choice, and the bit trick uses a bitset.