Skip to content

416. Partition Equal Subset Sum

Difficulty Topics

Description

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

partition-equal-subset-sum.py
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        total = sum(nums)
        target = total // 2
        if total & 1: return False

        bits = 1

        for x in nums:
            bits |= (bits << x)

        return (bits & (1 << target)) > 0
partition-equal-subset-sum.cpp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> bits(1);
        int total = 0;

        for (auto n:nums)
            bits |= bits << n, total += n;

        return !(total&1) && bits[total / 2];
    }
};