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]))
|