Leetcode - Partition Equal Subse

My code:

public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = sum; j >= nums[i - 1]; j--) {
                dp[j] |= dp[j - nums[i - 1]];
            }
        }
        
        return dp[sum];
    }
}

reference：
https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

首先，sum of total array should be even
其次，如果存在这么一种partition，那么，每个partition的和，一定是 sum / 2

然后，我们就可以用一种类似于 subset的方法，来求出，是否存在那么一组partition，他们的和是 sum / 2, 如果存在，一定还会有另外一组partition与之对应，和也是 sum / 2

所以用dp来解决这个问题。
然后我们的目的就是 sum / 2
所以他就是上限，任何 > sum / 2的序列，我们不感兴趣
一开始我们放入 nums[0]
然后是
nums[0], nums[1], nums[0] + nums[1] (assume they are all <= sum / 2)
nums[0], nums[1], nums[0] + nums[1], nums[2], nums[0] + nums[2]
nums[1] + nums[2], nums[0] + nums[1] + nums[2]
....

最后，我们需要求得， dp[sum / 2] 是否为 true

Anyway, Good luck, Richardo! -- 10/13/2016