416. Partition Equal Subset Sum (Medium)

https://leetcode.com/problems/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.

Solutions

class Solution {

    // This problem can be translated as find x numbers of which the total summation is sum/2,
    // where x is a variable and not determined; sum is the total summation of elements in nums.

    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        int len = nums.length;

        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) {
            return false;
        }

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

        // target 0, it is easy to get
        Arrays.fill(dp[0], true);

        // for the first column all set false, literally, elements in nums starts from 1 in dp
        for (int i = 0; i < target + 1; i++) {
            dp[i][0] = false;
        }

        dp[0][0] = true;

        // i is the target to achieve
        for (int i = 1; i < target + 1; i++) {

            // we add (j-1)th num to gain i
            for (int j = 1; j < len + 1; j++) {

                // can I use result of dp[i][j-1] or incorporate nums[j-1] to come up with a new combination.

                // 1. dp[i][j-1] is true which means elements in nums[0:j-2] can make sum to i, and we don't
                // have to use nums[j-1]
                if (dp[i][j - 1]) {
                    dp[i][j] = true;

                    continue;
                }

                // 2. dp[i - nums[j - 1]][j - 1] is true which means we can use nums[i-j], plus valid combination
                // of target i-nums[j-1] of which elements are selected from nums[0:j-2] to achieve target i.

                dp[i][j] = i >= nums[j - 1] && dp[i - nums[j - 1]][j - 1];
            }
        }

        return dp[target][len];
    }
}

Incorrect Solutions

class Solution {

    // Incorrection idea.

    // This problem can be translated as find x numbers of which the total summation is sum/2,
    // where x is a variable and not determined; sum is the total summation of elements in nums.

    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) {
            return false;
        }

        int target = sum / 2;

        for (int i = 0; i <= target; i++) {

        }

        boolean ans = false;

        return ans;
    }
}

References