分割等和子集

题目描述：
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例：
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

Java代码：

class Solution {
    public boolean find(int[] nums, int target, int index) {
        if(target == 0) return true;
        for(int i = index;i < nums.length;i++) {
            if(i > index && nums[i] == nums[i - 1]) continue;
            if(target - nums[i] < 0) return false;
            if(find(nums, target - nums[i], i + 1)) return true;
        }
        return false;
    }

    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int num : nums) total += num;
        Arrays.sort(nums);
        if((total & 1) == 1) return false;
        if(total == 0) return true;
        return find(nums, total / 2, 0);
    }

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if(len == 0) return false;

        int sum = 0;
        for(int num : nums) sum += num;
        if((sum & 1) == 1) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        if(nums[0] <= target) dp[nums[0]] = true;
        for(int i = 1;i < len;i++) {
            for(int j = target;nums[i] <= j;j--) {
                if(dp[target]) return true;
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        } 
        return dp[target];
    }
}