Cacher is the code snippet organizer for pro developers

/*
我们定义一个一维的dp数组，其中dp[i]表示数字i是否是原数组的任意个子集合之和，那么我们我们最后只需要返回dp[target]就行了。我们初始化dp[0]为true.由于题目中限制了所有数字为正数，那么我们就不用担心会出现和为0或者负数的情况。
那么关键问题就是要找出递归公式了，我们需要遍历原数组中的数字，对于遍历到的每个数字nums[i]，
我们需要更新我们的dp数组，要更新[nums[i], target]之间的值，那么对于这个区间中的任意一个数字j，
如果dp[j - nums[i]]为true的话，那么dp[j]就一定为true，于是地推公式如下：
dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)
*/
public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 1) return false;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        sum /= 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
}

public class Solution {
    // public boolean canPartition(int[] nums) {
    //     int s = 0;
    //     for(int n:nums){
    //         s += n;
    //     }
    //     if(s%2!=0) return false;
    //     s = s/2;
    //     boolean[] d = new boolean[s+1];
    //     d[0] = true;
    //     for(int i=0;i<nums.length;i++){
    //         for(int j=s;j>=0;j--){
    //             if(((j-nums[i])>=0)&&d[j-nums[i]]){
    //                 d[j] = true;
    //             }
    //         }
    //     }
    //     return d[s];
    // }
public boolean canPartition(int[] nums) {
        int sum=0;
        for(int n : nums)
            sum += n;
        
        if(sum%2==1)
            return false;
        
        return helper(nums, 0, 0, sum/2, new HashSet<Integer>());
    }
    
    private boolean helper(int[] nums, int index, int cur, int target, Set<Integer> set){
        if(set.contains(cur))
            return false;
        if(cur==target)
            return true;
        if(cur>target)
            return false;
        
        for(int i=index; i<nums.length; i++)
            if( helper(nums, i+1, cur+nums[i], target, set) )
                return true;
        
        set.add(cur);
        return false;
    }
    
    
    
}