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.

time o(n*sum); space(sum)

dp问题， dp[j] 就是能否有子集的和等于j true or false;, 子问题就是，

dp[j] == true if dp[j-nums[i]] == true 当前遍历到的数字是nums[i],

如果dp[j-nums[i]]是true，那么加上nums[i]后等于j肯定也是true

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