Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Based on the problem, we know if the sum of all elements in the array is odd, we cannot partition it to two equal subsets. So we first sum up all elements and check if the sum is even. After we pass the first check, our problem becomes if we can find a subset with sum half of the sum of all elements. Now we use DP. Here I iterate from target to a element, this is necessary because each number can only be used once, also it can help us to avoid some of the unnecessary iteration.

public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        boolean[] sums = new boolean[sum + 1];
        sums[0] = true;
        
        for (int n : nums) {
            for (int i = sum; i >= n; i--) {
                sums[i] |= sums[i - n];
            }
        }
        return sums[sum];
    }