Partition Equal Subset Sum

---

Partition Equal Subset Sum: 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

---

Try this Problem on your own or check similar problems:

1. Partition to K Equal Sum Subsets
2. Minimize the Difference Between Target and Chosen Elements
3. Maximum Number of Ways to Partition an Array

Solution:

Java

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
        sum += nums[i];
    }
    if(sum % 2 == 1)  return false;

    int halfSum = sum / 2;

    Set<Integer> set = new HashSet<>();
    set.add(0);

    for(int n : nums){
        for(int j = halfSum; j >= n; --j){
            if(set.contains(j-n)){
                set.add(j);
            }
        }
    }

    return set.contains(halfSum);
}

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let sum = nums.reduce((acc, num) => acc + num, 0);
  if (sum % 2 === 1) return false;

  let halfSum = sum / 2;

  let set = new Set();
  set.add(0);

  for (let num of nums) {
    let tempSet = new Set(set);
    for (let item of tempSet) {
      if (item + num <= halfSum) {
        set.add(item + num);
      }
    }
  }

  return set.has(halfSum);
};

Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 == 1:
            return False

        half_sum = total_sum // 2

        set_ = {0}

        for num in nums:
            temp_set = set(set_)
            for item in temp_set:
                if item + num <= half_sum:
                    set_.add(item + num)

        return half_sum in set_

C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }

        int halfSum = sum / 2;

        std::unordered_set<int> set;
        set.insert(0);

        for (int num : nums) {
            std::unordered_set<int> tempSet(set);
            for (int item : tempSet) {
                if (item + num <= halfSum) {
                    set.insert(item + num);
                }
            }
        }

        return set.count(halfSum) != 0;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n*S) where S == halfSum
• Space Complexity: O(S)

---

Explanation:

It's really similar to the Target Sum, we first check if sum of elements in the input array is divisible by 2, if not we immediately return false. If the sum is even, we check if we can add up to sum/2 using elements of the array. Note that this time we don't need the dp to track in how many ways we can reach the target, we only need a set that will tell us if we already can form j-n target, which basically means that if we add the current element, we could get j. At the end we check if we can get half of the target sum set.contains(halfSum). Note that we iterate first over the elements and then the target (in reverse order) which stops us from using the same element twice.