Partition Equal Subset Sum

Problem

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.

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.

Note:

• Each of the array element will not exceed 100.
• The array size will not exceed 200.

Solution

DP Solution

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

Analysis

This problem is similar to the typical backpack problem
To get the subset, we can either pick a number or not pick it
First we check the total sum and return false if it's not even
Then we have our target sum / 2 and create a dp array with that length
dp[i] represents if we can construct a subset with sum i
The init case for dp array is dp[0] = true, pick no number and we get sum 0
Then we loop through each num from nums and check each possible target
Hence, i is from target until the valid index i - num
If we don't pick that number, dp[i] won't change
If we pick that number, we need to see if we have its remaining, which is dp[i - num]