aboutsummaryrefslogtreecommitdiff
path: root/partition_equal_subset_sum.py
blob: 7f563b7dc7c1344d6f0006279b79fffddf21ce5e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 416. Partition Equal Subset Sum

"""
given an integer array 'nums', return true if you can partition the array
into two subsets such that the sum of the elements in both subsets is equal
or false otherwise
"""


class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        total_sum = sum(nums)
        if total_sum & 1:
            return False
        half_sum, dp = total_sum // 2, 1
        for n in nums:
            dp |= dp << n
        return dp & 1 << half_sum


if __name__ == "__main__":
    obj = Solution()
    print(obj.canPartition(nums=[1, 5, 11, 5]))
    print(obj.canPartition(nums=[1, 2, 3, 5]))