[Leetcode] 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.

Analysis:

The problem to have the two subset whose sums are equal is the same as the problem to find a subset whose sum is half of the total of the array which is a typical 0,1 knapsack problem: for a given nums[i], if it is included in the subset, then dp[i][j] = dp[i-1][j - nums[i]], otherwise, dp[i][j] = dp[i-1][j]. The dp transition function is  dp[i][j] = dp[i-1][j] || (j >=nums[i-1] && dp[i-1][j-nums[i-1]]). We can also write the dp algorithm with one dimension array:  dp[j] = dp[j] || (j >=nums[i-1] && dp[j-nums[i-1]]); 

Two dimension array:

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

One dimension array:

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