diff options
Diffstat (limited to 'partition_equal_subset_sum.py')
-rw-r--r-- | partition_equal_subset_sum.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/partition_equal_subset_sum.py b/partition_equal_subset_sum.py new file mode 100644 index 0000000..7f563b7 --- /dev/null +++ b/partition_equal_subset_sum.py @@ -0,0 +1,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])) |