Partition Equal Subset Sum

Problem

Given a non-empty array nums 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: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

 

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((acc, cur) => acc + cur, 0);
    if (sum % 2 !== 0) { // sum is odd, cannot have non-integer target
        return false;
    }
    const target = sum / 2;
    const dp = Array(target + 1)
        .fill(null)
        .map(() => Array(nums.length + 1).fill(false));

    for (let i = 0; i <= nums.length; i++) {
        dp[0][i] = true;
    }

    for (let i = 1; i <= target; i++) {
        for (let j = 1; j <= nums.length; j++) {
            if (nums[j - 1] > i) {
                dp[i][j] = dp[i][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1] || dp[i - nums[j - 1]][j - 1];
            }
        }
    }
    return dp[target][nums.length];
};

We will implement a DP solution. First, notice that this problem is equivalent to finding if there exists a subset of nums such that the sum of elements in the subset equals sum(nums) / 2. More specifically, if there exists such a subset s1 for sum(nums) = 2k, then sum(s1) = k, and so sum(nums - s1) = sum(s2) = sum(nums) - sum(s1) = 2k - k = k (where s1 and s2 make up nums). Let dp[i][j] be if there exists a subset of nums[0:j] such that the sum of elements in the subset equals i.

• For the base case:
  • If i = 0, then dp[0][j] = true since you can use the empty set to sum up to 0.
  • If j = 0, then dp[i][0] = false since you can't sum up to any value i > 0 using the empty set nums[0:0].
• For the recursive case, there are two possible outcomes for every element of nums, either include the element in our subset or exclude it.
  • If nums[j - 1] > i, it means the current element is larger then the target sum i, so it can only be excluded.
  • Otherwise, if either including or excluding the current element adds up to the sum i, then dp[i][j] is true (else false).

Optimization

We can optimize the above solution to use O(sum) space as follows:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((acc, cur) => acc + cur, 0);
    if (sum % 2 !== 0) {
        return false;
    }
    const target = sum / 2;
    const dp = Array(target + 1).fill(false);
    dp[0] = true;

    for (const n of nums) {
        for (let i = target; i >= 1; i--) {
            if (n <= i) {
                dp[i] = dp[i] || dp[i - n];
            }
        }
    }
    return dp[target];
};

Notice that for the inner-loop, we iterate backwards, which is necessary. Looking at the 2D solution, dp[i][j] relies on the value of the direct previous column from previous rows. Thus, we need to evaluate dp going from bottom to top instead of top to bottom in terms of i (ie. difference between dp[i - nums[j - 1]][j - 1] and dp[i - nums[j - 1]][j]).