Partition Equal Subset Sum

NeetCode: Partition Equal Subset Sum · LeetCode: 416. Partition Equal Subset Sum · Difficulty: Medium

Given an array nums of positive integers (the problem limits them to 100 each and the length to 200, so the total is at most 20000 and fits in an int), return true if it can be split into two subsets with equal sums.

Example

Text

Input:  nums = [1, 5, 11, 5]    Output: true     ([1, 5, 5] and [11])
Input:  nums = [1, 2, 3, 5]     Output: false

If the total is odd the answer is false. Otherwise the problem is to find a subset that sums to exactly total / 2; the remaining elements then sum to the other half.

Brute force: include or exclude each number

Java

class Solution {
    private boolean can(int[] nums, int i, int remaining) {
        if (remaining == 0) {
            return true;
        }
        if (i == nums.length) {
            return false;
        }
        if (nums[i] > remaining) {
            return can(nums, i + 1, remaining);
        }
        return can(nums, i + 1, remaining - nums[i]) || can(nums, i + 1, remaining);
    }

    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        return total % 2 == 0 && can(nums, 0, total / 2);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(solution.canPartition(new int[]{1, 2, 3, 5}));
        System.out.println(solution.canPartition(new int[]{1}));
        System.out.println(solution.canPartition(new int[]{2, 2}));
    }
}

Output

true
false
false
true

Each number is either in the target subset or not. Time: O(2^n). Space: O(n) stack.

Optimal: 1-D boolean knapsack

Let dp[s] be true if some subset of the numbers seen so far sums to exactly s. Start with dp[0] = true (the empty subset). For each number x, any reachable sum s - x makes s reachable, so set dp[s] |= dp[s - x]. Iterate s downwards from the target to x, so that x is used at most once; iterating upwards would reuse the already updated dp[s - x] within the same number.

Java

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        if (total % 2 != 0) {
            return false;
        }
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (dp[s - x]) {
                    dp[s] = true;
                }
            }
        }
        return dp[target];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(solution.canPartition(new int[]{1, 2, 3, 5}));
        System.out.println(solution.canPartition(new int[]{1}));
        System.out.println(solution.canPartition(new int[]{2, 2}));
    }
}

Output

true
false
false
true

Time: O(n · target) where target = sum / 2. This is pseudo-polynomial: it depends on the values, not only on n. Space: O(target). If x > target the inner loop s >= x never runs, so such numbers are skipped. A new boolean array starts all false.